网络流 poj 3308 最小割

t个样例

n*m的矩阵 L个伞兵

给出每行每列装激光的花费

伞兵的位置

要求杀死所有伞兵总费用为这些费用的乘积求花费最小

建图源点 -> 行 -> 列 -> 汇点

权花费 inf 花费

花费相乘等于 log(花费)相加都变成double 最后取e

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<queue>
  5 #include<math.h>
  6 
  7 using namespace std;
  8 
  9 int S,T,cnt;
 10 #define inf 100000000
 11 #define MAXN 2000
 12 #define MAXN1 3500
 13 int head[MAXN+10];
 14 int vis[MAXN+10];
 15 
 16 struct edg
 17 {
 18     int to,next;
 19     double w;
 20 }x[MAXN1*2];
 21 
 22 void add(int u,int v,double w)
 23 {
 24     x[cnt].next=head[u];
 25     x[cnt].to=v;
 26     x[cnt].w=w;
 27     head[u]=cnt++;
 28 }
 29 int bfs()
 30 {
 31     queue<int>q1;
 32     memset(vis,-1,sizeof(vis));
 33     vis[S]=0;
 34     q1.push(S);
 35 
 36     while(!q1.empty())
 37     {
 38         int now=q1.front();
 39         q1.pop();
 40         int j;
 41 
 42         for(j=head[now];j!=-1;j=x[j].next)
 43         {
 44             if(vis[x[j].to]<0&&x[j].w>0)
 45             {
 46                 vis[x[j].to]=vis[now]+1;
 47                 q1.push(x[j].to);
 48             }
 49         }
 50     }
 51     return vis[T]!=-1;
 52 
 53 }
 54 double dfs(int u,double w)
 55 {
 56     double ans=0;
 57     if(u==T)
 58         return w;
 59     int j;
 60     for(j=head[u];j!=-1;j=x[j].next)
 61     {
 62         if(vis[x[j].to]==vis[u]+1&&x[j].w>0)
 63         {
 64             double b=dfs(x[j].to,min(w-ans,x[j].w));
 65             x[j].w-=b;
 66             x[j^1].w+=b;
 67             ans+=b;
 68         }
 69     }
 70     return ans;
 71 }
 72 
 73 int main()
 74 {
 75     int t;
 76     scanf("%d",&t);
 77 
 78     while(t--)
 79     {
 80         int n,m,l,i;
 81         scanf("%d%d%d",&n,&m,&l);
 82         S=0,T=n+m+1;
 83         cnt=0;
 84         memset(head,-1,sizeof(head));
 85         for(i=1;i<=n;i++)
 86         {
 87             double a;
 88             scanf("%lf",&a);
 89             add(S,i,log(a)),add(i,S,0);
 90         }
 91         for(i=1;i<=m;i++)
 92         {
 93             double a;
 94             scanf("%lf",&a);
 95             add(i+n,T,log(a)),add(T,i+n,0);
 96         }
 97 
 98         for(i=1;i<=l;i++)
 99         {
100             int a,b;
101             scanf("%d%d",&a,&b);
102             add(a,b+n,inf);
103             add(b+n,a,0);
104         }
105         double ans=0;
106         while(bfs())
107              ans+=dfs(S,inf);
108 
109         printf("%.4lf
",exp(ans));
110     }
111     return 0;
112 }