比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
李奇文 |
运行时间 |
0.135 s |
代码语言 |
C++ |
内存使用 |
15.45 MiB |
提交时间 |
2025-08-13 09:27:37 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,S,P,ans,ca[N];
int hd[N],tot,tp,w[N],yj[N];
int a[N],dr[N],ins[N],dfn[N],low[N],s[N],cnt;
int sc,scc[N],sz[N];
struct node{
int to,nxt;
}e[N];
void add(int x,int y){
++tot;
e[tot].to=y;
e[tot].nxt=hd[x];
hd[x]=tot;
}
void tarjan(int u){
low[u]=dfn[u]=++cnt,s[++tp]=u,ins[u]=1;
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
if(dfn[v]==0){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(ins[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
++sc;
do{
scc[s[tp]]=sc;
sz[sc]++;
ins[s[tp]]=0;
}while(s[tp--]!=u);
}
}
vector<int> newe[N];
void spfa(){
ca[scc[S]]=w[scc[S]];
queue<int> q;
q.push(scc[S]);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<newe[u].size();i++){
int v=newe[u][i];
if(ca[u]+w[v]>ca[v]){
ca[v]=ca[u]+w[v];
q.push(v);
}
}
}
}
int main(){
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int hs,sh;
scanf("%d%d,",&hs,&sh);
add(hs,sh);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=n;i++){
for(int j=hd[i];j;j=e[j].nxt){
int v=e[j].to;
if(scc[i]==scc[v]) continue;
newe[scc[i]].push_back(scc[v]);
}
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
w[scc[i]]+=a[i];
}
scanf("%d%d",&S,&P);
for(int i=1;i<=P;i++){
scanf("%d",&dr[i]);
}
for(int i=1;i<=n;i++){
if(dr[i]) yj[scc[dr[i]]]=1;
}
spfa();
for(int i=1;i<=sc;i++){
if(yj[i]) ans=max(ans,ca[i]);
}
printf("%d",ans);
return 0;
}