记录编号	177865	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-08-12 20:27:02	内存使用	1.28 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
using namespace std;
int deep[502],s,t,as[502][502];
int n,m,flow,a,b,c,h;
bool bfs(int s,int t)
{
	memset(deep,-1,sizeof(deep));
	queue<int>q;
	deep[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int yu=q.front();
		q.pop();
		for(int i=1;i<=n;++i)
		{
			if(as[yu][i]&&deep[i]<0)
			{
				deep[i]=deep[yu]+1;
				q.push(i);
			}
		}
	}
	if(deep[t]>0) return 1;
	return 0;
}
int find(int s,int low)
{   int a=0;
	if(s==t) return low;
	for(int i=1;i<=n;++i)
	{
		if(as[s][i]&&deep[i]==deep[s]+1)
		{
			if(a=find(i,min(low,as[s][i])))
			{
				as[s][i]-=a;
				as[i][s]+=a;
				return a;
			}
		}
	}
	return 0;
}
int main()
{  freopen("ditch.in","r",stdin);
	freopen("ditch.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		as[a][b]+=c;
	}
	s=1;
	t=n;
	flow=0;
	while(bfs(s,t))
	{
		while(h=find(s,999999999)) flow+=h;
	}
	printf("%d",flow);
}