（网络流Dinic） poj 1273

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 0x7fffffff
queue<int> q;
int tab[250][250];
int dis[250];
int N,M,ANS;
int BFS()
{
     memset(dis,-1,sizeof(dis));
     dis[1]=0;
     q.push(1);
     while (!q.empty())
     {
           int x=q.front();
           q.pop();
           for (int i=1;i<=N;i++)
               if (dis[i]<0&&tab[x][i]>0)
               {
                  dis[i]=dis[x]+1;
                  q.push(i);
               }
     }
     if(dis[N]>0)
        return 1;
     else
        return 0;
}
int find(int x,int low)
{
    int a=0;
    if (x==N)return low;
    for (int i=1;i<=N;i++)
    if (tab[x][i]>0&&dis[i]==dis[x]+1&&(a=find(i,min(low,tab[x][i]))))
    {
       tab[x][i]-=a;
       tab[i][x]+=a;
       return a;
    }
    return 0;
}
int main()
{
    int f,t,flow,tans;
    while(scanf("%d%d",&M,&N)!=EOF)
    {
            memset(tab,0,sizeof(tab));
            for(int i=1;i<=M;i++)
            {
                  scanf("%d%d%d",&f,&t,&flow);
                  tab[f][t]+=flow;
            }
            ANS=0;
            while(BFS())
            {
                  while(tans=find(1,INF))ANS+=tans;
            }
            printf("%d\n",ANS);
    }
    return 0;
}