记录编号	339469	评测结果	AAAAAAAAAA
题目名称	花园的守护之神	最终得分	100
用户昵称	Hzoi_Queuer	是否通过	通过
代码语言	C++	运行时间	1.670 s
提交时间	2016-11-05 21:01:33	内存使用	49.87 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define LL long long
const int maxn=1005,maxe=499505*2;
struct Edge{
	int from,to,next;LL dis;
}E[maxe];
struct edge{
	int to,next;LL cap;
}e[maxe*2];
struct Node{
	int x;LL dis;
	Node(int a,LL b){x=a;dis=b;}
	bool operator < (const Node &a)const{
		return a.dis<dis;
	}
};
int n,m,s,t,len=0,Len=0,tot=0;
int head[maxn],Head[maxn],vis[maxn]={0};
LL dis[maxn];
void Insert(int x,int y,LL z){
	Len++;E[Len].from=x;E[Len].to=y;E[Len].dis=z;E[Len].next=Head[x];Head[x]=Len;
}
void Insert2(int x,int y,LL z){
	e[len].to=y;e[len].cap=z;e[len].next=head[x];head[x]=len;len++;
}
void Dijs(){
	memset(dis,0x3f,sizeof dis);
	priority_queue<Node> q;
	q.push(Node(s,0));dis[s]=0;
	while(!q.empty()){
		Node k=q.top();q.pop();
		if(k.x==t)return;
		if(dis[k.x]!=k.dis)continue;
		for(int i=Head[k.x];i!=-1;i=E[i].next){
			int j=E[i].to;
			if(dis[j]>dis[k.x]+E[i].dis){
				dis[j]=dis[k.x]+E[i].dis;
				q.push(Node(j,dis[j]));
			}
		}
	}
}
void Bfs(){
	memset(dis,0,sizeof dis);
	queue<int>q;q.push(s);vis[s]=tot;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i!=-1;i=e[i].next){
			int j=e[i].to;
			if(e[i].cap && vis[j]!=tot){
				q.push(j);vis[j]=tot;
				dis[j]=dis[x]+1;
			}
		}
	}
}
LL Dfs(int x,LL flow){
	if(x==t || !flow)return flow;
	LL cnt=0;
	for(int i=head[x];i!=-1;i=e[i].next){
		int j=e[i].to;
		if(e[i].cap && dis[j]==dis[x]+1){
			LL d=Dfs(j,min(flow,e[i].cap));
			e[i].cap-=d;e[i^1].cap+=d;
			flow-=d;cnt+=d;
			if(flow==0)break;
		}
	}
	dis[x]=-1;
	return cnt;
}
int main()
{
	freopen("greendam2002.in","r",stdin);
	freopen("greendam2002.out","w",stdout);
	fill(Head,Head+maxn,-1);
	fill(head,head+maxn,-1);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int x,y;LL z;
    for(int i=1;i<=m;i++){
		scanf("%d%d%lld",&x,&y,&z);
		Insert(x,y,z);Insert(y,x,z);
	}
	Dijs();
	for(int i=1;i<=m*2;i++){
		x=E[i].from,y=E[i].to;
		if(dis[x]+E[i].dis==dis[y])Insert2(x,y,1ll),Insert2(y,x,0ll);
	}
	LL cnt=0;
	while(1){
		tot++;
		Bfs();
		if(vis[t]!=tot){printf("%lld\n",cnt);break;}
		cnt+=Dfs(s,0x3f3f3f3f);
	}
    return 0;
}