记录编号	302139	评测结果	AAAAAAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2016-09-03 12:36:14	内存使用	14.24 MiB

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int MAX=500000+10;
int head[MAX]={0};
struct Edge{
	int t,next;
	Edge(){
		next=0;
	}
}A[MAX];
int dfn[MAX]={0};
int now[MAX]={0};
int low[MAX];
stack<int>s;
int nu[MAX];
bool ins[MAX]={0};
int ans=0;
int ind=0;
bool bar[MAX]={0};
int fa[MAX];
int vis[MAX]={0};
int maxx[MAX]={0};
struct T{
	int x,nn;
};
queue<int>q;
int read(){
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
void tarjan(int x){
	dfn[x]=low[x]=++ind;
	ins[x]=1;
	s.push(x);
	for(int i=head[x];i;i=A[i].next){
		int u=A[i].t;
		if(!dfn[u]){
			tarjan(u);
			if(low[u]<low[x])
				low[x]=low[u];
		}
		else if(ins[u]&&dfn[u]<low[x]){
			low[x]=dfn[u];
		}
	}
	if(dfn[x]==low[x]){
		int k;
		do{
			k=s.top();
			s.pop();
			ins[k]=false;
			if(k!=x){
				fa[k]=x;
				for(int j=head[k];j;j=A[j].next){
					if(head[x]){
						A[now[x]].next=j;
						now[x]=j;
					}
					else {
						head[x]=j;
						now[x]=j;
					}
				}
				nu[x]+=nu[k];
				nu[k]=0;
				if(bar[k]){
					bar[x]=true;
					bar[k]=false;
				}
				head[k]=0;
			}
		}while(k!=x);
	}
}
int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	int n,m;
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
		fa[i]=i;
	int x,y;
	for(int i=1;i<=m;i++){
		x=read();y=read();
		if(head[x]){
			A[now[x]].next=i;
			now[x]=i;
			A[i].t=y;
		}
		else {
			head[x]=i;
			now[x]=i;
			A[head[x]].t=y;
		}
	}
	for(int i=1;i<=n;i++)
		nu[i]=read();
	int s,p;
	s=read();p=read();
	for(int i=1;i<=p;i++)
		x=read(),bar[x]=1;
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	maxx[fa[s]]=nu[fa[s]];
	vis[fa[s]]=1;
	q.push(fa[s]);
	while(!q.empty()){
		int cd=q.front();
		q.pop();
		if(bar[cd]&&maxx[cd]>ans)
			ans=maxx[cd];
		for(int i=head[cd];i;i=A[i].next){
			int u=fa[A[i].t];
			if(maxx[cd]+nu[u]>maxx[u]&&fa[u]!=fa[cd]){
				maxx[u]=maxx[cd]+nu[u];
				if(!vis[u]){
					vis[u]=1;
					q.push(u);
				}
			}
		}
		vis[cd]=0;
	}
	printf("%d\n",ans);
return 0;
}