记录编号	302965	评测结果	AAAAAAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-09-04 19:20:35	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500010;
struct edge{
	int to,prev;
}e[maxn];
void insert(int,int,int*);
void Tarjan(int);
void SPFA(int);
int dfn[maxn],low[maxn],ww[maxn],a[maxn],origlast[maxn]={0},anolast[maxn]={0},belong[maxn],w[maxn]={0},q[maxn],dis[maxn];
bool ins[maxn]={false},inq[maxn]={false};
int n,m,len=0,tim=0,top=0,cnt=0,s,x,y,ans=0,head=0,tail=0;
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d",&x,&y);
		insert(x,y,origlast);
	}
	for(int i=1;i<=n;i++)scanf("%d",&ww[i]);
	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
	for(x=1;x<=n;x++)for(int i=origlast[x];i;i=e[i].prev){
		y=e[i].to;
		if(belong[x]!=belong[y])insert(belong[x],belong[y],anolast);
	}
	scanf("%d%d",&s,&m);
	SPFA(belong[s]);
	while(m--){
		scanf("%d",&x);
		ans=max(ans,dis[belong[x]]);
	}
	printf("%d",ans);
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
void insert(int x,int y,int *last){
	e[++len].to=y;
	e[len].prev=last[x];
	last[x]=len;
}
void Tarjan(int x){
	int y;
	dfn[x]=low[x]=++tim;
	a[++top]=x;
	ins[x]=true;
	for(int i=origlast[x];i;i=e[i].prev){
		y=e[i].to;
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y])low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		cnt++;
		do{
			y=a[top--];
			belong[y]=cnt;
			w[cnt]+=ww[y];
			ins[y]=false;
		}while(x!=y);
	}
}
void SPFA(int x){
	int y;
	memset(dis,-64,sizeof(dis));
	dis[x]=w[x];
	q[tail++]=x;
	while(head!=tail){
		x=q[head++];
		inq[x]=false;
		for(int i=anolast[x];i;i=e[i].prev){
			y=e[i].to;
			if(dis[y]<dis[x]+w[y]){
				dis[y]=dis[x]+w[y];
				if(!inq[y]){
					q[tail++]=y;
					inq[y]=true;
				}
			}
		}
	}
}
int hzoier=MAIN();
int main(){;}