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

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 215;
const int inf = 0x3f3f3f3f;
int n,m,q[MAXN],d[MAXN];


struct edge{
	int v,w,next;
}a[MAXN*4];
int first[MAXN],e=2;

void push(int u,int v,int w){
	a[e].v=v;
	a[e].w=w;
	a[e].next=first[u];
	first[u]=e++;
}

bool bfs(){
	memset(d,-1,sizeof(d));
	d[1]=1;
	int l=0,r=1;
	q[l]=1;
	while(l<r){
		int x=q[l++];
		if(x==n)return 1;
		for(int i=first[x];i;i=a[i].next){
			int v=a[i].v,w=a[i].w;
			if(d[v]==-1&&w){
				d[v]=d[x]+1;
				q[r++]=v;
			}
		}
	}
	return 0;
}

int dfs(int s,int cap){
	if(cap==0||s==n)return cap;
	int res=0;
	for(int i=first[s];i;i=a[i].next){
		int v=a[i].v,w=a[i].w;
		if(d[v]==d[s]+1&&w){
			int Min=min(cap-res,w);
			int w=dfs(v,Min);
			a[i].w-=w;
			a[i^1].w+=w;
			res+=w;
			if(res==cap)return cap;
		}
	}
	if(res==0)d[s]=-1;
	return res;
}

int cc(){
	freopen("ditch.in","r",stdin);
	
	freopen("ditch.out","w",stdout);
	
	scanf("%d%d",&m,&n);
	
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		
		push(u,v,w);
		
		push(v,u,0);
	}
	
	int ans=0;
	while(bfs())ans+=dfs(1,inf);
	
	printf("%d\n",ans);
}

int haha=cc();

int main(){
}