比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
左清源 |
运行时间 |
0.218 s |
代码语言 |
C++ |
内存使用 |
26.92 MiB |
提交时间 |
2025-08-13 09:24:29 |
显示代码纯文本
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=5e5+10;
vector<int>G[N],F[N];
int n,m,st,dfn[N],low[N],col[N];
int cnt,mk[N],stk[N],top,p,ans,ind[N];
int scc,val[N],w[N],dp[N],vis[N];
void add(int x,int y){
G[x].push_back(y);
}
void link(int x,int y){
F[x].push_back(y);
}
void tarjan(int u){
dfn[u]=low[u]=++cnt;
mk[u]=1,stk[++top]=u;
for(auto v:G[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(mk[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
scc++;
while(stk[top+1]!=u){
int v=stk[top--];
mk[v]=0;col[v]=scc;
val[scc]+=w[v];
}
}
return;
}
void dfs(int x){
vis[x]=1;
for(auto y:F[x])if(!vis[y])dfs(y);
return;
}
queue<int>q;
void topsort(int s){
q.push(s);
dp[s]=val[s];
while(q.size()){
int x=q.front();q.pop();
for(auto y:F[x]){
if(!vis[y])continue;
dp[y]=max(dp[y],dp[x]+val[y]);
ind[y]--;
if(!ind[y])q.push(y);
}
}
for(int i=1;i<=scc;i++)if(mk[i])ans=max(ans,dp[i]);
return;
}
int main(){
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d %d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++)scanf("%d",w+i);
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
scanf("%d %d",&st,&p);
for(int i=1;i<=p;i++){
int x;scanf("%d",&x);
mk[col[x]]=1;
}
for(int i=1;i<=n;i++){
for(auto j:G[i]){
if(col[i]!=col[j]){
link(col[i],col[j]);
//cout<<col[i]<<" "<<col[j]<<endl;
}
}
}
dfs(col[st]);
for(int i=1;i<=n;i++){
for(auto j:G[i]){
if(col[i]!=col[j]&&vis[col[i]]&&vis[col[j]]){
ind[col[j]]++;
}
}
}
topsort(col[st]);
printf("%d\n",ans);
return 0;
}