poj3308Paratroopers(dinic）

http://poj.org/problem?id=3308

给两个定义

最小割：对于图中的两个点(一般为源点和汇点)来说，如果把图中的一些边去掉，如果它们之间无法连通的话，则这些边组成的集合就叫为割了。如果这些边有权值，最小割就是指权值之和最小的一个割。

最大流最小割：应用于网络中，指总流量不超过链路可承载的最大值，且在每条子路径上取尽可能少的流量。对任意一个只有一个源点一个汇点的图来说，从源点到汇点的最大流等于最小割。

之前做二分图的时候看过一篇文章现在依旧看这篇http://ip96cns.blog.163.com/blog/static/170095192201117465473/

设置超级源点及超级汇点行和列看做结点每一个点看做一个边把行和列两个结点连起来

这个题是求最小乘积刚开始还以为样例答案错了呢用一个log函数就可以转换为相加

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<cmath>
  7 #include<queue>
  8 #define N 2510
  9 #define M 400100
 10 #define INF 0x3f3f3f3f
 11 #define eps 1e-8
 12 using namespace std;
 13 struct node
 14 {
 15     int u,v,next;
 16     double w;
 17 }edge[M];
 18 int head[N],t,vis[N],pp[N],dis[N];
 19 void init()
 20 {
 21     t=0;
 22     memset(head,-1,sizeof(head));
 23 }
 24 void add(int u,int v,double w)
 25 {
 26     edge[t].u = u;
 27     edge[t].v = v;
 28     edge[t].w = w;
 29     edge[t].next = head[u];
 30     head[u] = t++;
 31     edge[t].u = v;
 32     edge[t].v = u;
 33     edge[t].w = 0;
 34     edge[t].next = head[v];
 35     head[v] = t++;
 36 }
 37 int bfs(int e)
 38 {
 39     int i,u;
 40     double w;
 41     memset(dis,-1,sizeof(dis));
 42     queue<int>q;
 43     q.push(0);
 44     dis[0]=  0;
 45     while(!q.empty())
 46     {
 47         u = q.front();
 48         q.pop();
 49         for(i = head[u] ; i != -1 ; i = edge[i].next)
 50         {
 51             int v = edge[i].v;
 52             w = edge[i].w;
 53             if(w>eps&&dis[v]<0)
 54             {
 55                 dis[v] = dis[u]+1;
 56                 q.push(v);
 57             }
 58         }
 59     }
 60     if(dis[e]>0) return 1;
 61     return 0;
 62 }
 63 double dfs(int u,double te,int e)
 64 {
 65     int i;
 66     double s;
 67     if(u==e) return te;
 68     for(i = head[u] ; i != -1 ; i = edge[i].next)
 69     {
 70         int v = edge[i].v;
 71         double w = edge[i].w;
 72         if(w>eps&&dis[v]==dis[u]+1&&(s=dfs(v,min(te,w),e)))
 73         {
 74             edge[i].w-=s;
 75             edge[i^1].w+=s;
 76             return s;
 77         }
 78     }
 79     return 0;
 80 }
 81 int main()
 82 {
 83     int i,n,m,o,k,a,b;
 84     double p;
 85     cin>>o;
 86     while(o--)
 87     {
 88         cin>>n>>m>>k;
 89         init();
 90         for(i = 1; i <= n ; i++)
 91         {
 92             cin>>p;
 93             add(0,i,log(p));
 94         }
 95         for(i = 1; i <= m ; i++)
 96         {
 97             cin>>p;
 98             add(n+i,n+m+1,log(p));
 99         }
100         for(i = 1 ; i <= k ; i++)
101         {
102             cin>>a>>b;
103             add(a,n+b,INF);
104         }
105         double s = 0,ss=0;
106         while(bfs(n+m+1))
107         {
108             ss = dfs(0,INF,n+m+1);
109             if(ss>eps)
110             s+=ss;
111             else break;
112         }
113 
114         printf("%.4f
",exp(s));
115     }
116     return 0;
117 }

View Code