#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#define arr 210
#define INT_MAX 214748364
using namespace std;
int map[arr][arr],pre[arr],flow[arr];
int n,m,start,end;
int BFS()
{
    int i,j,k,v,u;
    memset(pre,-1,sizeof(pre));
    for(i=1;i<=n;i++) flow[i]=INT_MAX;
    queue<int>que;
    pre[start]=0;
    que.push(start);
    while(!que.empty())
    {
       v=que.front();
       que.pop();  //清空队列； 
       for(i=1;i<=n;i++)
       {
           u=i;
           if(u==start||pre[u]!=-1||map[v][u]==0) continue;
           pre[u]=v;
           flow[u]=min(flow[v],map[v][u]);
           que.push(u);
       }
    }
    if(flow[end]==INT_MAX) return -1;
    return flow[end];
}
int Edmonds_Karp()
{
    int i,j,k,temp,now,last,ans=0;
    while(1)
    {
        temp=BFS();
        if(temp==-1) break;
        ans+=temp;
        now=end;
        while(now!=start)
        {
              last=now;
              now=pre[now];
              map[now][last]-=temp;
              map[last][now]+=temp;
        }
    }
    return ans;
}
        
int main()
{
    int i,j,k,u,v,w;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(map,0,sizeof(map));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&v,&u,&w);
            map[v][u]+=w;//前面已经全部初始化了； 
        }
        start=1; end=n;
        int ans=Edmonds_Karp();
        printf("%d\n",ans);
    }
}
        

• Re:在北大OJ里的第一道网络流题，小小的纪念一下，代码留下 (33) possibility 2010-08-05 09:27:10