POJ 1273 Drainage Ditches 最大流

http://poj.org/problem?id=1273
题目大意：
给你N条路径（有重边），和M个点，求以1为源点，M为汇点的最大流。
思路：
第一题最大流问题，直接用Edmonds-Karp算法即可

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=200+10;
const int INF=0x1fffffff;
int flow[MAXN][MAXN],cap[MAXN][MAXN],n,m,a[MAXN],p[MAXN];
int Ekarp()
{
	queue<int> q;
	memset(flow,0,sizeof(flow));
	int f=0;
	while(true)
	{
		memset(a,0,sizeof(a));
		a[1]=INF;
		q.push(1);
		while(!q.empty())
		{
			int from=q.front(); q.pop();
			for(int to=1;to<=n;to++) if(!a[to] && cap[from][to] > flow[from][to])
			{
				p[to]=from;   q.push(to);
				a[to]=min(a[from],cap[from][to]-flow[from][to]);
			}
		}
		if(a[n]==0) break;
		for(int i=n;i!=1;i=p[i])
		{
			flow[ p[i] ][i] +=a[n];
			flow[i] [ p[i] ]-=a[n];
		}
		f+=a[n];
	}
	return f;
}
int main()
{
	while(~scanf("%d%d",&m,&n))//和题目相反，习惯M是边
	{
		memset(cap,0,sizeof(cap));
		for(int i=0;i<m;i++)
		{
			int from,to,cost;
			scanf("%d%d%d",&from,&to,&cost);
			cap[from][to]+=cost;
		}
		printf("%d\n",Ekarp());
	}
	return 0;
}

POJ 1273 Drainage Ditches 最大流

原文：http://blog.csdn.net/murmured/article/details/19510513