比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
zhyn |
运行时间 |
0.230 s |
代码语言 |
C++ |
内存使用 |
28.65 MiB |
提交时间 |
2025-08-13 10:26:49 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
int n,m;
int s,p;
int v[maxn];
int st[maxn],d[maxn],l[maxn],id[maxn];
bool in[maxn];
int sum[maxn];
bool bar[maxn];
vector<int> bs;
int top=0,cnt=0,tot=0;
vector<int> e[maxn];
struct nd{int to;};
vector<nd> g[maxn];
int deg[maxn];
int dis[maxn];
void tar(int u){
d[u]=l[u]=++tot;
st[++top]=u;
in[u]=true;
for(int to:e[u]){
if(!d[to]){
tar(to);
l[u]=min(l[u],l[to]);
}else if(in[to]){
l[u]=min(l[u],d[to]);
}
}
if(l[u]==d[u]){
cnt++;
int x;
do{
x=st[top--];
in[x]=false;
id[x]=cnt;
sum[cnt]+=v[x];
}while(x!=u);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
e[a].push_back(b);
}
for(int i=1;i<=n;i++)cin>>v[i];
cin>>s>>p;
bs.resize(p);
for(int i=0;i<p;i++){
cin>>bs[i];
bar[bs[i]]=true;
}
for(int i=1;i<=n;i++)if(!d[i])tar(i);
for(int u=1;u<=n;u++){
for(int to:e[u]){
if(id[u]!=id[to]){
g[id[u]].push_back({id[to]});
deg[id[to]]++;
}
}
}
int scc=id[s];
memset(dis,-0x3f,sizeof(dis));
dis[scc]=sum[scc];
queue<int> q;
for(int i=1;i<=cnt;i++)if(deg[i]==0)q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
for(nd nde:g[u]){
int v=nde.to;
if(dis[v]<dis[u]+sum[v])dis[v]=dis[u]+sum[v];
deg[v]--;
if(deg[v]==0)q.push(v);
}
}
int ans=0;
for(int b:bs)ans=max(ans,dis[id[b]]);
cout<<ans<<endl;
return 0;
}