POJ 1273

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define maxn 200 + 5
#define inf 0x7fffffff
int m, n;
int c[maxn][maxn],pre[maxn];
int Edmonds_Karp(int s,int t)
{
  int minflow,maxflow = 0;
  while(1)
  {
  minflow = inf;
  memset(pre, 0 , sizeof(pre));
  queue <int> q;
  q.push(s);
  while(!q.empty())    //BFS找增广路
  {
    int x = q.front();
    q.pop();
    if(x == t) break;
    for(int i = 1;i <= n;i ++)
	{
	  if(c[x][i] > 0&& pre[i] == 0)
	  {
	    pre[i] = x;   //记录前驱
	    q.push(i);
	  }
	}
  }
  if(pre[t] == 0)  break;  //终点无前驱，即没有增广路
  for(int i = t; i != s;i = pre[i])
  minflow = min(minflow, c[pre[i]][i]);
  for(int i = t; i != s;i = pre[i])
  {
   c[pre[i]][i] -= minflow;
   c[i][pre[i]] += minflow;
  }
  maxflow += minflow;
  }
  return maxflow;
}
int main()
{
	int from,to,cc;
	while(scanf("%d%d", &m, &n) != EOF)
	{
	  memset(c, 0, sizeof(c));
	  while(m --)
	  {
	    scanf("%d%d%d", &from, &to, &cc);
	    c[from][to] += cc;  //可能有多条路径
      }
	  int ans = Edmonds_Karp(1,n);
	  printf("%d\n", ans);
	}
	return 0;
}