学步园

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N=1100, inf=1<<30;
int pre[N], map[N][N];
int n,m;
bool vis[N];
struct node{
    int x,val;
    node() {}
    node(int a, int b): x(a), val(b) {}
};

int min(int a, int b){
    return a<b?a:b;
}

int bfs()
{
    queue<node> v;
    node cur;
    v.push( node(1,inf) );
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    vis[1]=1;
    while(!v.empty())
    {
        cur=v.front(); v.pop();
        if(cur.x==n) break;
        for(int i=1;i<=n;i++)
            if( map[cur.x][i] && !vis[i])
            {
                v.push( node(i, min(cur.val, map[cur.x][i])) );
                pre[i]=cur.x; vis[i]=1;
            }
    }
    if(cur.x==n && cur.x!=1) return cur.val;
    else return -1;
}

int EK()
{
    int next,res,flow,ans;
    ans=0;
    while( (flow=bfs())!=-1 )
    {
        next=n;
        while(next!=1)
        {
        	res=pre[next];
            map[res][next]-=flow;
            map[next][res]+=flow;
            next=res;
        }
        ans+=flow;
    }
    return ans;
}

int main()
{
	// freopen("in","r",stdin);
 //    freopen("out","w",stdout);
    int i,a,b,c;
    while(~scanf("%d%d",&m,&n))
    {
        memset(map,0,sizeof(map));
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &c);
            map[a][b]+=c;
        }
        printf("%d\n", EK());
    }
    return 0;
}