记录编号	338486	评测结果	AAAAAAAAAA
题目名称	花园的守护之神	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.195 s
提交时间	2016-11-05 10:48:25	内存使用	30.87 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>
#define INF ((~((1)<<(31)))>>(1))
#define heap_tag pairing_heap_tag
using namespace std;
using namespace __gnu_pbds;
const int maxn=1010,maxe=500010;
struct edge1{int from,to,prev;long long dis;}e1[maxe<<1];
struct edge2{int to,cap,prev;}e2[maxe<<1];
struct node{
	int x;
	long long dis;
	node(int x,long long dis):x(x),dis(dis){}
	bool operator<(const node &a)const{return dis>a.dis;}
};
void addedge1(int,int,long long);
void addedge2(int,int,int);
void Dijkstra(int,long long*);
int Dinic();
void bfs();
int dfs(int,int);
int n,m,s,t,last1[maxn]={0},len1=0,last2[maxn],len2=0,now[maxn],d[maxn],q[maxn],head,tail,x,y;
long long dis[maxn],redis[maxn],z;
__gnu_pbds::priority_queue<node,less<node>,heap_tag>::point_iterator iter[maxn];
bool vis[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("greendam2002.in","r",stdin);
	freopen("greendam2002.out","w",stdout);
#endif
	memset(last2,-1,sizeof(last2));
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld",&x,&y,&z);
		addedge1(x,y,z);
		addedge1(y,x,z);
	}
	Dijkstra(s,dis);
	Dijkstra(t,redis);
	for(int i=1;i<=(m<<1);i++)if(dis[e1[i].from]+e1[i].dis+redis[e1[i].to]==dis[t]){
		addedge2(e1[i].from,e1[i].to,1);
		addedge2(e1[i].to,e1[i].from,0);
	}
	printf("%d",Dinic());
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge1(int x,int y,long long z){
	e1[++len1].from=x;
	e1[len1].to=y;
	e1[len1].dis=z;
	e1[len1].prev=last1[x];
	last1[x]=len1;
}
void addedge2(int x,int y,int z){
	e2[len2].to=y;
	e2[len2].cap=z;
	e2[len2].prev=last2[x];
	last2[x]=len2++;
}
void Dijkstra(int x,long long *dis){
	memset(vis,0,sizeof(vis));
	__gnu_pbds::priority_queue<node,less<node>,heap_tag>q;
	memset(dis,63,sizeof(long long)*maxn);
	dis[x]=0;
	for(int i=1;i<=n;i++)if(i!=x)iter[i]=q.push(node(i,INF));
	iter[x]=q.push(node(x,0));
	while(!q.empty()){
		x=q.top().x;
		q.pop();
		if(vis[x])continue;
		vis[x]=true;
		for(int i=last1[x];i;i=e1[i].prev)if(dis[e1[i].to]>dis[x]+e1[i].dis){
			dis[e1[i].to]=dis[x]+e1[i].dis;
			q.modify(iter[e1[i].to],node(e1[i].to,dis[e1[i].to]));
		}
	}
}
int Dinic(){
	int ans=0;
	for(;;){
		bfs();
		if(d[t]==INF)break;
		memset(now,0,sizeof(now));
		ans+=dfs(s,INF);
	}
	return ans;
}
void bfs(){
	int x;
	fill_n(d+1,n,INF);
	d[s]=0;
	head=tail=0;
	q[tail++]=s;
	while(head!=tail){
		x=q[head++];
		for(int i=last2[x];i!=-1;i=e2[i].prev)if(e2[i].cap>0&&d[e2[i].to]==INF){
			d[e2[i].to]=d[x]+1;
			q[tail++]=e2[i].to;
		}
	}
}
int dfs(int x,int delta){
	if(x==t||!delta)return delta;
	int flow=0,f;
	for(int i=(now[x]?now[x]:last2[x]);i!=-1;i=e2[i].prev)if(e2[i].cap>0&&d[e2[i].to]==d[x]+1){
		now[x]=i;
		f=dfs(e2[i].to,min(delta,e2[i].cap));
		if(!f)continue;
		e2[i].cap-=f;
		e2[i^1].cap+=f;
		flow+=f;
		delta-=f;
		if(!delta)break;
	}
	return flow;
}