poj 1459 Power Network(增广路)
题目:http://poj.org/problem?id=1459
题意:有一些发电站,消耗用户和中间线路,求最大流。。
加一个源点,再加一个汇点。。
其实,过程还是不大理解。。
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 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。