记录编号 177905 评测结果 AAAAAAAAAAAA
题目名称 草地排水 最终得分 100
用户昵称 Gravatar炎帝 是否通过 通过
代码语言 C++ 运行时间 0.004 s
提交时间 2015-08-12 21:02:36 内存使用 0.33 MiB
显示代码纯文本
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int tot,head[205],m,n,a,b,c;
int deep[205],flow,h;
struct dd
{
	int zhong;
	int juli;
	int next;
}jie[700];
void add(int x,int y,int z)
{
	jie[tot].zhong=y;
	jie[tot].juli=z;
	jie[tot].next=head[x];
	head[x]=tot++;
}
bool bfs()
{
	queue<int>q;
	memset(deep,0,sizeof(deep));
	deep[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int yu=q.front();
		q.pop();
		for(int i=head[yu];i!=-1;i=jie[i].next)
		{
			if(jie[i].juli&&!deep[jie[i].zhong])
			{
				deep[jie[i].zhong]=deep[yu]+1;
				q.push(jie[i].zhong);
			}
		}
	}
	if(deep[n]>0) return true;
	return false;
}
int find(int s,int low)
{
	if(s==n) return low;
	for(int i=head[s];i!=-1;i=jie[i].next)
	{
		if(jie[i].juli&&deep[jie[i].zhong]==deep[s]+1)
		{
			if(a=find(jie[i].zhong,min(low,jie[i].juli)))
			{
				jie[i].juli-=a;
				jie[i^1].juli+=a;
				return a;
			}
		}
	}
	return 0;
}
int main()
{   freopen("ditch.in","r",stdin);
	freopen("ditch.out","w",stdout);
	while(scanf("%d%d",&m,&n)!=EOF)
	{   memset(head,-1,sizeof(head));
	    flow=0;
		for(int i=1;i<=m;++i)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
			add(b,a,0);
		}
		while(bfs())
		   while(h=find(1,99999999)) flow+=h;
		printf("%d\n",flow);
	}
}