比赛 |
至少完成十道练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
Ostmbh |
运行时间 |
0.049 s |
代码语言 |
C++ |
内存使用 |
20.34 MiB |
提交时间 |
2017-05-22 17:32:50 |
显示代码纯文本
#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;
}