记录编号	149086	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-02-18 16:15:25	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
const int inf=0x3f3f3f3f;
int n,m,ans,len=1,g[201],d[201],q[201],to[405],cap[405],next[405];
bool bfs(){
	int l=1,r=1;
	memset(d,0,sizeof d),d[1]=1,q[1]=1;
	while(l<=r){
		int x=q[l++];
		for(int i=g[x];i;i=next[i])
			if(!d[to[i]]&&cap[i]) 
				q[++r]=to[i],d[to[i]]=d[x]+1; 
	}
	return d[n];
}
int dfs(int x,int y){
	if(x==n||!y) return y;int flow=0;
	for(int i=g[x];i;i=next[i]){
		if(!cap[i]||d[to[i]]!=d[x]+1) continue;
		int f=dfs(to[i],std::min(y,cap[i]));
		flow+=f,y-=f,cap[i]-=f,cap[i^1]+=f;
		if(!y) break;
	}
	return flow;
}
int main(){
	freopen("ditch.in","r",stdin);
	freopen("ditch.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int x,y,z;m--;){
		scanf("%d%d%d",&x,&y,&z);
		to[++len]=y,next[len]=g[x],cap[len]=z,g[x]=len;
		to[++len]=x,next[len]=g[y],cap[len]=0,g[y]=len;
	}
	while(bfs()) ans+=dfs(1,inf);
	printf("%d",ans);
}