记录编号	317771	评测结果	AAAAAAAAAA
题目名称	花园的守护之神	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	1.802 s
提交时间	2016-10-08 15:15:42	内存使用	27.76 MiB

#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
const int inf = INT_MAX;
const int maxn = 1024;
const int maxm = 1000010;
int ans,n,m,S,T,cnt;
int q[maxn],head1[maxn],head2[maxn],dis[maxn];
struct Edge{
	int from,to,next,v;
}G[maxm],g[maxm];
void add1(int u,int v,int w){
	G[++cnt].to = v;
	G[cnt].from = u;
	G[cnt].next = head1[u];
	head1[u] = cnt;
	G[cnt].v = w;
}
void add2(int u,int v,int w){
	g[++cnt].to = v;
	g[cnt].next = head2[u];
	head2[u] = cnt;
	g[cnt].v = w;
}
struct Node{
	int num,dis;
	bool friend operator < (const Node &a,const Node &b){
		return a.dis > b.dis;
	}
	Node(){}
	Node(int a,int b){num = a;dis = b;}
};
void dijkstra(){
	priority_queue<Node>q;
	memset(dis,0x3f,sizeof dis);
	dis[S] = 0;
	q.push(Node(S,0));
	while(!q.empty()){
		Node x = q.top();q.pop();
		if(dis[x.num] != x.dis) continue;
		for(int i = head1[x.num];i;i = G[i].next){
			if( dis[G[i].to] > dis[x.num] + G[i].v){
				dis[G[i].to] = dis[x.num] + G[i].v;
				q.push(Node(G[i].to,dis[G[i].to]));
			}
		}
	}
}
bool bfs(){
	int l=0,r=1;
	memset(dis,-1,sizeof(dis));
	dis[S] = 0;q[0] = S;
	while(l != r){
		int x = q[l++];
		for(int i = head2[x]; i ;i = g[i].next)
			if(g[i].v && dis[ g[i].to ] == -1){
				dis[ g[i].to ] = dis[x] + 1;
				q[r++] = g[i].to;
			}
	}
	return dis[T] != -1;
}
int dfs(int x,int f){
	if(x == T) return f;
	int w,used = 0;
	for(int i = head2[x];i;i=g[i].next){
		if(dis[x] + 1 == dis[g[i].to]){
			w = f - used;
			w = dfs(g[i].to,min(g[i].v,w));
			g[i].v -= w;
			g[i^1].v += w;
			used += w;
			if(used == f) return f;
		}
	}
	if( !used ) dis[x] = -1;
	return used;
}
int main(){
	freopen("greendam2002.in","r",stdin);
	freopen("greendam2002.out","w",stdout);
	read(n);read(m);read(S);read(T);
	for(int i=1,u,v,w;i<=m;i++){
		read(u);read(v);read(w);
		add1(u,v,w);add1(v,u,w);
	}
	dijkstra();
	int t = cnt;cnt = 1;
	for(int i = 1;i <= t; ++i){
		if(dis[ G[i].from ] + G[i].v == dis[ G[i].to ]){
			add2(G[i].from,G[i].to,1);
			add2(G[i].to,G[i].from,0);
		}
	}
	while(bfs())ans+=dfs(S,inf);
	printf("%d\n",ans);
	return 0;
}