#include "iostream"
const int INFI=1<<30;
int rest[202][202];
int arc[202][202];
int N,M;
int ans;
bool Used[202];
int DFS(int root,int min)
{
     if(root==N-1)return min;
     for(int i=0;i<N;i++)
     {
         if(rest[root][i]>0&&Used[i]==0)
         {
             min<?=rest[root][i];
             Used[i]=1;
             int inc=DFS(i,min);
             Used[i]=0;
             if(inc>0)
             {
                 rest[root][i]-=inc;
                 rest[i][root]+=inc;
                 return inc;
             }
         }
     }
     return 0;
}
main()
{
    while(scanf("%d %d",&M,&N)!=EOF)
    {
        memset(arc,0,sizeof(arc));
        memset(rest,0,sizeof(rest));
        memset(Used,0,sizeof(Used));
        for(int i=0;i<M;i++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            arc[a-1][b-1]>?=c;
            rest[a-1][b-1]>?=c;
        }
        ans=0;
        int inc;
        while(1)
        {
            Used[0]=1;
            inc=DFS(0,INFI);
            Used[0]=0;
            if(inc==0)break;
            ans+=inc;
        }
        printf("%d\n",ans);
    }
}
      

• 原来是没有剪支正确，每一次增广每个点都只需检查一次。 (0) smallbox 2009-02-06 14:39:15
  • Re:原来是没有剪支正确，每一次增广每个点都只需检查一次。 (49) slp 2009-11-16 22:00:24
• Re:为什么别人用DFS增广可以我的却超时，第一次做这种题，各位看一下是哪里不对 (32) sw_shizi 2010-07-31 21:23:42
  • 就是去掉回溯的vis重置 (18) Snow_storm 2010-10-20 17:13:10