#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 210
int tu[N][N],flow[N];
short que[N],flag[N],cl[N];
int e,s,min;
void qu(int n)//入队
{
    e++;
    if(e>=N)
    {
        e=1;
    }
    que[e]=n;
 }
int dequ()//出队
{
    int t;
    s++;
    t=que[s];
    if(s>=N)
    {
        s=1;
    }
    return t;
    
}
int bfs(int m)
{
    int i,t,f;
   
    for(i=1;i<=m;i++)
    {
        flag[i]=0;
        cl[i]=0;
    }
     qu(1);
     flag[1]=1;
     f=0;
     flow[1]=10000001;
    while(e!=s)
    {
        t=dequ();
        if(t==m)
        {
            f=1;
            break;
        }
        for(i=2;i<=m;i++)
        {
            
                if(tu[t][i]!=0&&flag[i]!=1)//cl[]存父结点  flow[]存最小值
                {
                    cl[i]=t;
                    flag[i]=1;
                    if(tu[t][i]<flow[t])
                    {
                        flow[i]=tu[t][i];
                    }
                    else
                    {
                        flow[i]=flow[t];
                    }
                    qu(i);//入队
                }
            
        
        }
      
    }
     if(f==1)
     {
         return flow[m];
     }
     else
     {
         return 0;
     }
}
int main(int argc, char** argv) {

    int m,n,i,a,b,val,temp,sum;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        sum=0;
        e=0;
        s=0;
        memset(tu,0,sizeof(tu));
        for(i=1;i<=n;++i)
        {
            scanf("%d %d %d",&a,&b,&val);
            tu[a][b]+=val;
        }
        
        while((temp=bfs(m))!=0)
        {
         
            for(i=m;cl[i]!=0;i=cl[i])//更新
            {
                tu[cl[i]][i]-=temp;
                tu[i][cl[i]]+=temp;
            }
           // update(m);
            sum+=temp;
        }
        printf("%d\n",sum);
        
    }
    return (EXIT_SUCCESS);
}
//好诡异呀！

• Re:跪求超时原因～～！ 经过比较 貌似和ac代码差不多啊！ (14) foolishair 2012-04-14 21:21:58