本文主要是介绍POJ 3308 Paratroopers（最小割+Dinic），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3308
题意：外星人来攻打地球了。。。外星人派了一些伞兵来攻占地球的兵工场，兵工厂是一个矩形网格，伞兵会降落在兵工厂的某个位置。地球人有激光武器，可以杀死一行或者一列的所有敌人。但是每个激光武器安置在每行每列的费用都是不同的。伞兵很厉害只要一个就可以消灭兵工厂，所以，现在要部署一套激光系统使得伞兵一降落就可以消灭所有敌人。并且要求费用最少。
题解：
每个伞兵要用安置在其行上或者其列上的激光武器消灭。将矩阵的每行每列都视为一个点，将源点与“行点”相连，将汇点与“列点”相连对于伞兵降落的某个位置，将其行点和列点连接。根据割的性质，源点与汇点必不连通，因此割边集中必定存在S->R、R->C、C->T 其一。为了求得最小容量，将R->C 的容量设为无穷大，则其不可能被选中。这样割边集为S->R 与C->T的集合，也就是选中了行或列。此时求得的最小割即为花费最小的方案。
注意：1.花费是权值的乘积，可以用log和exp转化为加的形式。2.double的精度问题，据说有个2被原则，即eps取保留位数的2倍，所以取1e-8。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int MAXN=500+50*2+10;
const double INF=1e8;
const double eps=1e-8;
double g[MAXN][MAXN];
int level[MAXN];
int cur[MAXN];
int N,S,E;double precision(double x)
{return fabs(x)<eps?0:x;
}int BFS()
{memset(level,-1,sizeof(level));level[S]=0;queue<int>que;que.push(S);while(!que.empty()){int u=que.front();que.pop();for(int v=0;v<N;v++){if(level[v]<0&&precision(g[u][v])>0.0){level[v]=level[u]+1;que.push(v);}}}if(level[E]>0) return 1;return 0;
}double DFS(int x,double low)
{if(x==E) return low;for(int i=cur[x];i<N;i++){cur[x]=i;if(precision(g[x][i])>0.0&&level[i]==level[x]+1){double a=DFS(i,min(low,g[x][i]));if(precision(a)>0.0){g[x][i]-=a;g[i][x]+=a;return a;}}}return 0;
}double Dinic()
{double ans=0;while(BFS()){memset(cur,0,sizeof(cur));double tans;while(tans=DFS(S,INF)) ans+=tans;}return ans;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int tcase;scanf("%d",&tcase);while(tcase--){int m,n,l;scanf("%d%d%d",&m,&n,&l);N=m+n+2;S=0;E=N-1;for(int i=0;i<N;i++){for(int j=0;j<N;j++)g[i][j]=0.0;}for(int i=1;i<=m;i++){double val;scanf("%lf",&val);g[S][i]=log(val);}for(int i=1;i<=n;i++){double val;scanf("%lf",&val);g[m+i][E]=log(val);}for(int i=1;i<=l;i++){int x,y;scanf("%d%d",&x,&y);g[x][m+y]=INF;}/*for(int i=0;i<N;i++){for(int j=0;j<N;j++)cout<<g[i][j]<<" ";cout<<endl;}*/printf("%.4lf\n",exp(Dinic()));}return 0;
}这篇关于POJ 3308 Paratroopers（最小割+Dinic）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
