记录编号	261809	评测结果	AAAAAAAAAA
题目名称	花园的守护之神	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.991 s
提交时间	2016-05-18 17:48:41	内存使用	31.13 MiB

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=10010;
const LL inf=1e15;
int n,m,tot=0,tot2=1,h[maxn],vis[maxn],cur[maxn],s,t;
struct edge{int to,next,w,f;}G[maxn*100],g[maxn*100];
LL dis1[maxn],dis2[maxn];

void add(int x,int y,int z){
	G[++tot].to=y;G[tot].next=h[x];h[x]=tot;G[tot].w=z;
	G[++tot].to=x;G[tot].next=h[y];h[y]=tot;G[tot].w=z;
	G[tot].f=y; G[tot-1].f=x;
}

void spfa(LL dis[],int s){
	for (int i=1;i<=n;++i) dis[i]=inf,vis[i]=0;
	deque<int>q; q.push_front(s); vis[s]=1; dis[s]=0;
	while (!q.empty()){
		int u=q.front(); q.pop_front(); vis[u]=0;
		for (int i=h[u];i;i=G[i].next){
			int v=G[i].to;
			if (dis[v]>dis[u]+G[i].w){
				dis[v]=dis[u]+G[i].w;
				if (!vis[v]){
					vis[v]=1;
					if (!q.empty()&&dis[v]<dis[q.front()]) q.push_front(v);
					else q.push_back(v);
				}
			}
		}
	}
}

void add2(int x,int y,int z){
	g[++tot2].to=y;g[tot2].next=h[x];h[x]=tot2;g[tot2].w=z;
	g[++tot2].to=x;g[tot2].next=h[y];h[y]=tot2;g[tot2].w=0;
}

bool bfs(){
	for (int i=1;i<=n;++i) vis[i]=-1;
	queue<int>q; q.push(s); vis[s]=0;
	while (!q.empty()){
		int u=q.front(); q.pop();
		for (int i=h[u];i;i=g[i].next){
			int v=g[i].to;
			if (vis[v]==-1&&g[i].w>0){
				vis[v]=vis[u]+1;
				q.push(v);
			}
		}
	}return vis[t]!=-1;
}

int dfs(int x,int f){
	if (x==t||!f) return f;
	int w,used=0;
	for (int i=cur[x];i;i=g[i].next)
	    if (vis[g[i].to]==vis[x]+1){
			w=f-used;
			w=dfs(g[i].to,min(w,g[i].w));
			g[i].w-=w; g[i^1].w+=w;
			used+=w; if (used==f) return f;
			if (g[i].w) cur[x]=i;
	    }
	if (!used) vis[x]=-1;
	return used;
}

void dinic(){
	int ret=0;
	while (bfs()){
		for (int i=1;i<=n;++i) cur[i]=h[i];
		ret+=dfs(s,0x7fffffff/3);
	}printf("%d",ret);
}

int main(){
	freopen("greendam2002.in","r",stdin);
	freopen("greendam2002.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for (int i=1;i<=m;++i){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	spfa(dis1,s); //spfa(dis2,t);
	for (int i=1;i<=n;++i) h[i]=0;
	for (int i=1;i<=tot;++i)
	    if (dis1[G[i].f]+G[i].w==dis1[G[i].to]) add2(G[i].f,G[i].to,1);
	dinic();
}