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

• 狂ft!!!多谢styc,我自己无论如何也想不到这儿错。 (0) tengshengbo 2005-08-09 13:51:03
  • ................. (0) frkstyc 2005-08-09 13:51:31