记录编号	430270	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-07-29 16:19:26	内存使用	1.08 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
#define pos(i,a,b) for(LL i=(a);i<=(b);i++)
#define N 40100
const int inf=0x7fffffff;
struct haha{
	int next,to,w;
}edge[N];
int head[N],cnt;
int n,m;
void add(int u,int v,int w){
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
int dep[N];
bool bfs(){
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(1);
	dep[1]=1;
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=head[now];i!=-1;i=edge[i].next){
			int to=edge[i].to,w=edge[i].w;
			if(w&&(!dep[to])){
				dep[to]=dep[now]+1;
				q.push(to);
				if(to==n){
					return 1;
				}
			}
		}
	}
	return 0;
}
int dfs(int now,int f){
	if(now==n){
		return f;
	}
	int tmp=f;
	for(int i=head[now];i!=-1;i=edge[i].next){
		int to=edge[i].to,w=edge[i].w;
		if(w&&tmp&&dep[to]==dep[now]+1){
			int k=dfs(to,min(tmp,w));
			if(!k){
				dep[to]=0;
				continue;
			}
			edge[i].w-=k;
			edge[i^1].w+=k;
			tmp-=k;
		}	
	}
	return f-tmp;
}
int ans;
int main(){
	freopen("ditch.in","r",stdin);
	freopen("ditch.out","w",stdout);
	memset(head,-1,sizeof(head));
	scanf("%d%d",&m,&n);
	pos(i,1,m){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,0);
	}
	while(bfs()){
		ans+=dfs(1,inf);
	}
	cout<<ans;
	return 0;
}