比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAWAAAA |
题目名称 |
抢掠计划 |
最终得分 |
90 |
用户昵称 |
会挽弯弓满月 |
运行时间 |
0.039 s |
代码语言 |
C++ |
内存使用 |
3.96 MiB |
提交时间 |
2025-08-13 10:21:01 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int read(){
int x=0,f=1;
char c=getchar();
while(c<48||c>57){
if(c==45) f=-1;
c=getchar();
}
while(c>=48&&c<=57){
x=x*10+c-48;
c=getchar();
}
return f*x;
}
int n,m;
struct node{
int from,to,nxt;
}e[N],E[N];
int h[N],tot;
int H[N];
void add(int u,int v){
e[++tot].from=u;
e[tot].to=v;
e[tot].nxt=h[u];
h[u]=tot;
return;
}
void ADD(int u,int v){
E[++tot].from=u;
E[tot].to=v;
E[tot].nxt=H[u];
H[u]=tot;
return;
}
//0:ATM 1:酒吧
int val[N],kind[N];
int S,num;
int dfn[N],low[N];
int color,cnt;
int q[N],top;
int co[N],k[N],vl[N];
int S_now;
void tarjan(int u){
dfn[u]=low[u]=++cnt;q[++top]=u;
int v;
for(int i=h[u];i;i=e[i].nxt){
v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!co[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
co[u]=++color;
if(kind[u]) k[color]=1;
if(u==S) S_now=color;
vl[color]+=val[u];
while(q[top]!=u){
co[q[top]]=color;
vl[color]+=val[q[top]];
if(kind[q[top]]) k[color]=1;
if(q[top]==S) S_now=color;
top--;
}
top--;
}
return;
}
void build(){
tot=0;
int u,v;
for(int i=1;i<=m;i++){
u=co[e[i].from];
v=co[e[i].to];
if(u!=v) ADD(u,v);
}
return;
}
int sum[N];
bool vis[N];
void bfs(int u){
queue<int> Q;
int v;
Q.push(u);
while(Q.size()){
u=Q.front();
Q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=H[u];i;i=E[i].nxt){
v=E[i].to;
sum[v]=max(sum[v],sum[u]+vl[v]);
Q.push(v);
}
}
return;
}
int main(){
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
n=read();m=read();
int x,y,z;
for(int i=1;i<=m;i++){
x=read();y=read();
add(x,y);
}
for(int i=1;i<=n;i++) val[i]=read();
S=read();num=read();
for(int i=1;i<=num;i++){
x=read();
kind[x]=1;
}
tarjan(S);
build();
sum[S_now]=vl[S_now];
bfs(S_now);
int ans=0;
for(int i=1;i<=color;i++){
if(k[i]==1) ans=max(ans,sum[i]);
}
printf("%d",ans);
return 0;
}