poj1459(最大流算法 强大漂亮)

#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;
}