记录编号	339459	评测结果	AAAAAAAAAA
题目名称	花园的守护之神	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	1.982 s
提交时间	2016-11-05 20:57:59	内存使用	27.58 MiB

#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 2010
#define inf 0x7f7f7f7f
#define ll long long
#define min(a,b) ((a)<(b)?(a):(b))
int n,m,st,ed,len,head[maxn],d[maxn],num;
ll dis[maxn];
struct edge{
	int to,next,from,up;
	ll dis;
}b[2001000],a[2001000];
int read(){
	int x,f=1;
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;
	x=ch-'0';
	while(ch=getchar(),ch<='9'&&ch>='0')x=x*10+ch-'0';
	return x*f;
}
void insert1(int x,int y,ll z){
	len++;b[len].from=x;b[len].to=y;b[len].dis=z;b[len].next=head[x];head[x]=len;
}
void insert2(int x,int y,int z){
	num++;a[num].to=y;a[num].next=head[x];a[num].up=z;head[x]=num;
	num++;a[num].to=x;a[num].next=head[y];a[num].up=0;head[y]=num;
}
void spfa(){
	std::deque<int>q;
	bool f[maxn]={0};
	memset(dis,0x7f,sizeof dis);
	dis[st]=0;f[st]=1;
	q.push_back(st);
	while(!q.empty()){
		int x=q.front();q.pop_front();
		f[x]=0;
		for(int i=head[x];i;i=b[i].next){
			int to=b[i].to;
			if(dis[to]>dis[x]+b[i].dis){
				dis[to]=dis[x]+b[i].dis;
				if(!f[to]){
					f[to]=1;
					if(!q.empty()&&dis[to]<dis[q.front()])
					q.push_front(to);
					else q.push_back(to);
				}
			}
		}
	}
}
bool bfs(){
	memset(d,-1,sizeof d);
	std::queue<int>q;
	d[st]=0;q.push(st);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=a[i].next){
			int to=a[i].to;
			if(a[i].up&&d[to]==-1){
				d[to]=d[x]+1;
				q.push(to);
			}
		}
	}
	if(d[ed]==-1)return 0;
	else return 1;
}
int dfs(int x,int low){
	if(x==ed||low==0)return low;
	int totf=0;
	for(int i=head[x];i;i=a[i].next){
		int to=a[i].to;
		if(a[i].up&&d[to]==d[x]+1){
			int f=dfs(to,min(low,a[i].up));
			a[i].up-=f;a[i^1].up+=f;
			low-=f;totf+=f;
			if(low==0)return totf;
		}
	}
	d[x]=-1;
	return totf;
}
int ma(){
	freopen("greendam2002.in","r",stdin);
	freopen("greendam2002.out","w",stdout);
	n=read();m=read();st=read();ed=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		insert1(x,y,z);insert1(y,x,z);
	}
	spfa();
	memset(head,0,sizeof head);
	num=1;
	for(int i=1;i<=len;i++)
	if(dis[b[i].from]+b[i].dis==dis[b[i].to]){
		insert2(b[i].from,b[i].to,1);
	}
	int ans=0;
	while(bfs())ans+=dfs(st,inf);
	printf("%d",ans);
	//while(1);
}
int mo=ma();
int main(){;}