本文主要是介绍POJ 3308 最小割模型，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
还是棋盘上打外星人，这次不是最小点覆盖了，
给每个枪一个费用，选择一些行和列，最小费用打掉外星人
费用为所有费用的积
化费用积为 log 之和 最大流解决。
建图：
s -> 行 -> 列 -> t 行列之间若有外形人 连一条容量无限大的边。（意思尾费用无限大）
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
using namespace std;#define ll long long
#define P pair<int,int>
#define PDI pair<double,int>
#define fst first
#define sec second
#define MS(x) memset(x,0,sizeof(x))
#define INF 0x3f3f3f3f
#define MAX 300struct edge
{int to;double cap;int rev;
};vector<edge> G[MAX];
int level[MAX];
int iter[MAX];void addEdge(int from,int to,double cap)
{G[from].push_back((edge){to,cap,G[to].size()});G[to].push_back((edge){from,0.0,G[from].size()-1});
}void bfs(int s)
{memset(level,-1,sizeof(level));queue<int> que;level[s]=0;que.push(s);while(!que.empty()){int v=que.front();que.pop();for(int i=0;i<G[v].size();i++){edge &e=G[v][i];if(e.cap>0&&level[e.to]<0){level[e.to]=level[v]+1;que.push(e.to);}}}
}double dfs(int v,int t,double f)
{if(v==t)return f;for(int &i=iter[v];i<G[v].size();i++){edge &e=G[v][i];if(e.cap>0&&level[v]<level[e.to]){double d=dfs(e.to,t,min(f,e.cap));if(d>0){e.cap-=d;G[e.to][e.rev].cap+=d;return d;}}}return 0.0;
}double max_flow(int s,int t)
{double flow=0;while(1){bfs(s);if(level[t]<0) return flow;MS(iter);double f;while((f=dfs(s,t,INF))>0)flow+=f;}
}
int main()
{int cas;//freopen("acm.in","r",stdin);scanf("%d",&cas);while(cas--){for(int i=0;i<MAX;i++)G[i].clear();int n,m,l;scanf("%d%d%d",&n,&m,&l);int s,t;s=0,t=n+m+1;for(int i=0;i<n;i++){double ttt;scanf("%lf",&ttt);addEdge(s,i+1,log(ttt));}for(int i=0;i<m;i++){double ttt;scanf("%lf",&ttt);addEdge(1+n+i,t,log(ttt));}for(int i=0;i<l;i++){int f,t;scanf("%d%d",&f,&t);addEdge(f,n+t,INF);}double ans=max_flow(s,t);printf("%.4f\n",exp(ans));}return 0;
}
这篇关于POJ 3308 最小割模型的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
