记录编号	325637	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-10-20 07:33:23	内存使用	0.29 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510,maxe=510;
struct edge{int to,cap,prev;}e[maxe<<1];
int n,m,last[maxn],len=0,s,t,d[maxn],now[maxn],q[maxn],head,tail,x,y,z;
void addedge(int,int,int);
void insert(int,int,int);
int Dinic();
void bfs();
int dfs(int,int);
int main(){
#define MINE
#ifdef MINE
	freopen("ditch.in","r",stdin);
	freopen("ditch.out","w",stdout);
#endif
	memset(last,-1,sizeof(last));
	scanf("%d%d",&m,&n);
	s=1;
	t=n;
	while(m--){
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
	}
	printf("%d",Dinic());
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge(int x,int y,int z){
	insert(x,y,z);
	insert(y,x,0);
}
void insert(int x,int y,int z){
	e[len].to=y;
	e[len].cap=z;
	e[len].prev=last[x];
	last[x]=len++;
}
int Dinic(){
	int ans=0;
	for(;;){
		bfs();
		if(d[t]==0x3f3f3f3f)break;
		memset(now,0,sizeof(now));
		ans+=dfs(s,~(1<<31));
	}
	return ans;
}
void bfs(){
	int x;
	memset(d,63,sizeof(d));
	d[s]=0;
	head=tail=0;
	q[tail++]=s;
	while(head!=tail){
		x=q[head++];
		for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]>d[x]+1){
			d[e[i].to]=d[x]+1;
			q[tail++]=e[i].to;
		}
	}
}
int dfs(int x,int delta){
	if(x==t||!delta)return delta;
	int flow=0,f;
	for(int i=(now[x]?e[now[x]].prev:last[x]);i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]==d[x]+1){
		now[x]=i;
		f=dfs(e[i].to,min(delta,e[i].cap));
		if(!f)continue;
		e[i].cap-=f;
		e[i^1].cap+=f;
		flow+=f;
		delta-=f;
		if(!delta)break;
	}
	return flow;
}