#include<iostream> #include<cstdio> #include<string.h> #include<cmath> using namespace std; int n,n1,n2,m,ans,s,t,g,h; int d[500]/*路径*/,a[150][150],f[150][150],pre[150]/*增广路的前节点*/,c[150]/*路径最大可增广量*/; int main() { while(scanf("%d %d %d %d",&n,&n1,&n2,&m)==4){ ans=0; memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); s=n+1;t=n+2; int i,j,k,u,v,z; for(i=1;i<=m;i++){ while (getchar()!='('); scanf("%d,%d)%d",&u,&v,&z); a[u+1][v+1]=z; } for(i=1;i<=n1;i++){ while (getchar()!='(');//分号别掉了,意思完全不一样. scanf("%d)%d",&u,&z); a[s][u+1]=z; } for(i=1;i<=n2;i++){ while (getchar()!='('); scanf("%d)%d",&u,&z); a[u+1][t]=z; } while (1){ memset(pre,0,sizeof(pre));//其他? g=0;h=1;d[1]=s;c[s]=100000000;c[t]=0; pre[s]=s;//首先将s入队,否则下面是根据pre[]判断是否入队//初始化必须将下面判断的都重新考虑一遍 while (g<h&&pre[t]==0){//找出增广路 g++; for(i=1;i<=n+2;i++) if(pre[i]==0){//防止重复造成死循环,仔细想想,这样做是不会造成有增广路却找不到的情况,因为如果进入i后能找到增广路,那么原来i已经有增广路了,i也能够找到 if(a[d[g]][i]-f[d[g]][i]>0){ d[++h]=i; c[i]=c[d[g]]; if(c[i]>a[d[g]][i]-f[d[g]][i]) c[i]=a[d[g]][i]-f[d[g]][i]; pre[i]=d[g]; }else if(f[i][d[g]]>0){ d[++h]=i; c[i]=c[d[g]]; if(c[i]>f[i][d[g]]) c[i]=f[i][d[g]]; pre[i]=-d[g]; } } } if(pre[t]!=0){//增广 g=t; while (g!=s){//因为s肯定是向外的所以pre[g]只可能为s不为-s if(pre[g]>0) f[pre[g]][g]+=c[t]; if(pre[g]<0) f[g][-pre[g]]-=c[t]; g=abs(pre[g]); } ans+=c[t]; }else break; } printf("%d\n",ans); } return 0; } |
|
来自: goodwangLib > 《C#》