记录编号	303965	评测结果	AAAAAAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	100
用户昵称	kxxy	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2016-09-06 21:30:13	内存使用	12.21 MiB

#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
using namespace std;
const int maxn=500010;
struct Edge
{
	int to,next;
	Edge(){next=0;}
}A[maxn];
int dfn[maxn]={0},low[maxn],now[maxn]={0},fa[maxn],head[maxn];
int money[maxn],n,m,S,p,bar[maxn]={0},ind=0,ans=0;
int maxx[maxn]={0};
bool ins[maxn]={0},vis[maxn]={0};
queue<int>q;
stack<int>s;
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].to;
		if(!dfn[u])
		{
			tarjan(u);
			if(low[x]>low[u])
				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;
					}
				}
				money[x]+=money[k];
				money[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);
	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].to=y;
		}
		else
		{
			head[x]=i;
			now[x]=i;
			A[head[x]].to=y;
		}
	}
	for(int i=1;i<=n;i++)
		money[i]=read();
	S=read(),p=read();
	for(int i=1;i<=p;i++)
	{
		int barr;
		barr=read();
		bar[barr]=1;
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	maxx[fa[S]]=money[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].to];
			if(maxx[cd]+money[u]>maxx[u]&&fa[u]!=fa[cd])
			{
				maxx[u]=maxx[cd]+money[u];
				if(!vis[u])
				{
					vis[u]=1;
					q.push(u);
				}
			}
		}
		vis[cd]=0;
	}
	cout<<ans<<endl;
	return 0;
}