poj 1459 Power Network(增广路)

浏览数：11 / 时间：2015年06月09日

题意：有一些发电站，消耗用户和中间线路，求最大流。。

加一个源点，再加一个汇点。。

其实，过程还是不大理解。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 
 8 const int INF=1<<29;
 9 int cap[110][110],flow[110][110];
10 
11 int Edmonds_Karp(int s,int t,int n)
12 {
13     int a[110],p[110];
14     int f;
15     queue<int>q;
16     memset(flow,0,sizeof(flow));
17     f=0;
18     while(1)
19     {
20         memset(a,0,sizeof(a));
21         a[s]=INF;
22         q.push(s);
23         while(!q.empty())
24         {
25             int u=q.front();
26             q.pop();
27             for(int v=1; v<=n; v++)
28             if(!a[v]&&cap[u][v]>flow[u][v])
29             {
30                 p[v]=u; q.push(v);
31                 a[v]=min(a[u],cap[u][v]-flow[u][v]);
32             }
33         }
34         if(a[t]==0) break;
35         for(int u=t; u!=s; u=p[u])
36         {
37             flow[p[u]][u]+=a[t];
38             flow[u][p[u]]-=a[t];
39         }
40         f+=a[t];
41     }
42     return f;
43 }
44 int main()
45 {
46     int n,np,nc,m;
47     int u,v,w,i;
48     char s[20];
49     while(~scanf("%d%d%d%d",&n,&np,&nc,&m))
50     {
51         memset(cap,0,sizeof(cap));
52         for(i=0; i<m; i++)
53         {
54             scanf("%s",s);
55             sscanf(s,"(%d,%d)%d",&u,&v,&w);
56             u++; v++;
57             cap[u][v]+=w;
58         }
59         for(i=0; i<np; i++)
60         {
61             scanf("%s",s);
62             sscanf(s,"(%d)%d",&v,&w);
63             v++;
64             cap[0][v]+=w;
65         }
66         for(i=0; i<nc; i++)
67         {
68             scanf("%s",s);
69             sscanf(s,"(%d)%d",&u,&w);
70             u++;
71             cap[u][n+1]+=w;
72         }
73         printf("%d\n",Edmonds_Karp(0,n+1,n+1));
74     }
75     return 0;
76 }