比赛 20160902 评测结果 AWWWWWWWAW
题目名称 抢掠计划 最终得分 20
用户昵称 Ostmbh 运行时间 0.041 s
代码语言 C++ 内存使用 16.59 MiB
提交时间 2016-09-02 21:45:33
显示代码纯文本
#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};
struct T{
	int x,nn;
};
queue<T>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);
	T c;
	c.nn=nu[fa[s]];
	c.x=fa[s];
	q.push(c);
	vis[fa[s]]=1;
	ans=0;
	while(!q.empty()){
		T cd=q.front();
		q.pop();
		if(bar[cd.x]&&cd.nn>ans)
			ans=cd.nn;
		for(int i=head[cd.x];i;i=A[i].next){
			int u=A[i].t;
			if(!vis[u]&&cd.nn+nu[u]>cd.nn){
				vis[u]=1;
				T cdc;
				cdc.nn=cd.nn+nu[u];
				cdc.x=u;
				q.push(cdc);
			}
		}
		vis[cd.x]=0;
	}
	printf("%d\n",ans);
return 0;
}