#include <iostream>
#include <cstdio>
using namespace std;
typedef int Graph[200][200];
typedef int Path[200];
Graph map,flow;
int n,s,t;
int EK()
{
    int i, j, k=0, c, head, tail;
    Graph R;         
    Path prev, visit, Q;   
    for (i = 0; i < n; i++) 
    {
        for (j = 0; j < n; j++) 
        {
            flow[i][j] = 0;
            R[i][j] = map[i][j];
        }
    }
    while (true) {
        head = tail = 0;
        memset(visit, false, sizeof(visit)); 
        Q[tail++] = s;
        prev[s]   = -1;
        visit[s]  = 1;
        while (head < tail) {
            k = Q[head++];               
            for (i = 0; i < n; i++) 
            {
                if (!visit[i] && R[k][i] > 0) 
                {
                    visit[i] = 1;
                    prev[i]  = k;
                    if (i == t) break;
                    if(tail>=0) Q[tail++] = i;
                }
            }
            if(i==t) break;
        }
         if (!visit[t]) break;
        c = 1000000;
        j = t;
        while (j != s) {
            i = prev[j];
            if(c>R[i][j]) c=R[i][j];
            j = i;
        }
        j = t;
        while (j != s) {
            i = prev[j];
            flow[i][j] = flow[i][j] + c;
            flow[j][i] = -flow[i][j];
            R[i][j] = map[i][j] - flow[i][j];
            R[j][i] = map[j][i] - flow[j][i];   
            j = i;
        }
    }
    c = 0;
    for (i = 0; i < n; i++) {
        c += flow[s][i];
    }
    return c;
}


int main()
{
    while(scanf("%d",&n))
    {
		n=n+2;
        int i,j;
        memset(map,0,sizeof(map)); 
        s=n-2;
        t=n-1;
        int np,nc,m;
        scanf("%d%d%d",&np,&nc,&m);
        int u,v,z;
        char c[52];
        for(i=0;i<m;i++)
        {
            memset(c,0,sizeof(c));
            scanf("%s",&c);
            j=1;
            u=0;
            v=0;
            z=0;
            while(c[j]!=',')
            {
               u=u*10+c[j]-'0';
               j++;
            } 
            j++;  
            while(c[j]!=')')
            {
               v=v*10+c[j++]-'0';
            }
            j++;    
            while(c[j]!=0)
               z=z*10+c[j++]-'0';
            if(u!=v)
            {
                map[u][v]=z;
            }     
		//cout<<u<<" "<<v<<" "<<z<<endl;
        }
        for(i=0;i<np;i++)
        {
             memset(c,0,sizeof(c));
            scanf("%s",&c);
            j=1;
            u=0;
            z=0;
            while(c[j]!=')')
            {
               u=u*10+c[j]-'0';
               j++;
            }    
            j++;
            while(c[j]!=0)
            {
               z=z*10+c[j]-'0';
               j++;
            }    
            map[s][u]=z; 
		//	cout<<s<<" "<<u<<" "<<z<<endl;
        }
        for(i=0;i<nc;i++)
        {
            memset(c,0,sizeof(c));
            scanf("%s",&c);
            j=1;
            u=0;
            z=0;
            while(c[j]!=')')
               u=u*10+c[j++]-'0';
            j++;
            while(j<strlen(c))
               z=z*10+c[j++]-'0';
            map[u][t]=z;
		//	cout<<u<<" "<<t<<" "<<z<<endl;
        }      
        int result=EK();
        cout<<result<<endl;
    }
    return 0;
}        
          

• 就改一个地方，while(scanf("%d",&n))->while(scanf("%d",&n)!=EOF) (3710) frkstyc 2005-08-09 13:40:18
  • 狂ft!!!多谢styc,我自己无论如何也想不到这儿错。 (0) tengshengbo 2005-08-09 13:51:03
    • ................. (0) frkstyc 2005-08-09 13:51:31
• 很感谢师兄的网络流算法模版 (91) xemo 2005-08-09 15:37:08
  • 不谢不谢。 (95) tengshengbo 2005-08-09 17:21:36
  • 很感谢师兄的网络流算法模版. (0) Bupt_Pig 2006-03-21 20:47:16