记录编号	412079	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-06-07 19:34:59	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=215;
const int inf=0x7fffffff;
int m,n,adj[N],d[N],e=1;
struct node{int qi,zhong,flow,next;}s[N<<1];
inline int min(int a,int b){return a<b?a:b;}
inline void add(int qi,int zhong,int flow)
{
	s[++e].qi=qi;s[e].zhong=zhong; 
	s[e].next=adj[qi];s[e].flow=flow;
	adj[qi]=e;
}
queue<int>q;
bool bfs()
{
	memset(d,-1,sizeof(d));
	q.push(1);d[1]=1;
	while(!q.empty())
	{
		int rt=q.front();q.pop();
		for(int i=adj[rt];i;i=s[i].next)
		{
			int u=s[i].zhong;
			if(d[u]==-1&&s[i].flow)
			{
				d[u]=d[rt]+1;
				q.push(u);
			}
		}
	}
	return d[m]==-1?0:1;
}
int dfs(int rt,int maxf)
{
	if(rt==m||maxf==0)return maxf;
	int ret=0;
	for(int i=adj[rt];i;i=s[i].next)
	{
		if(s[i].flow)
		{
			int u=s[i].zhong;
			if(d[u]!=d[rt]+1)continue;
			int f=dfs(u,min(s[i].flow,maxf));
			maxf-=f;ret+=f;
			s[i].flow-=f;s[i^1].flow+=f;
			if(!maxf)break;
		}
	}
	if(!ret)d[rt]=-1;
	return ret;
}
int loooop()
{
	//freopen("Lex.txt","r",stdin);
	freopen("ditch.in","r",stdin);
	freopen("ditch.out","w",stdout);
	scanf("%d%d",&n,&m);
	int a,b,c;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);add(b,a,0);
	}
	int ret=0;
	while(bfs())ret+=dfs(1,inf);
	printf("%d\n",ret);
}
int t=loooop();
int main(){;}