比赛 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;
}