比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 ChenBp 运行时间 0.057 s
代码语言 C++ 内存使用 3.85 MiB
提交时间 2025-08-13 10:37:52
显示代码纯文本
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
const int N = 500005;
struct node {
    int head[N], nxt[N], to[N], num = 0;
    void add(int u, int v) {
        num++;
        nxt[num] = head[u];
        to[num] = v;
        head[u] = num;
    }
} g1, g2;

int dfn[N], low[N], belong[N], cnt = 0, scc = 0;
stack<int> s;
bool ins[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    s.push(u);
    ins[u] = true;

    for (int i = g1.head[u]; i; i = g1.nxt[i]) {
        int v = g1.to[i];
        if (!dfn[v]) {
            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]) {
        scc++;
        int x;
        do {
            x = s.top();
            s.pop();
            ins[x] = false;
            belong[x] = scc;
        } while (x != u);
    }
}
int bar[N], in[N], atm[N];
long long gatm[N], dis[N];
queue<int> q;
int main() {
    freopen("atm.in", "r", stdin);
    freopen("atm.out", "w", stdout);
    int n, m, s, p;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g1.add(u, v);
    }
    for (int i = 1; i <= n; i++) {
        cin >> atm[i];
    }
    cin >> s >> p;
    for (int i = 1; i <= p; i++) {
        cin >> bar[i];
    }
    tarjan(s);
    for (int i = 1; i <= n; i++) {
        if (belong[i] == 0)
            continue;
        for (int j = g1.head[i]; j; j = g1.nxt[j]) {
            int v = g1.to[j];
            if (belong[v] == 0)
                continue;
            if (belong[i] != belong[v]) {
                g2.add(belong[i], belong[v]);
                in[belong[v]]++;
            }
        }
        gatm[belong[i]] += atm[i];
    }
    dis[belong[s]] = gatm[belong[s]];
    q.push(belong[s]);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = g2.head[u]; i; i = g2.nxt[i]) {
            int v = g2.to[i];
            if (dis[v] < dis[u] + gatm[v]) {
                dis[v] = dis[u] + gatm[v];
            }
            if (--in[v] == 0) {
                q.push(v);
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= p; i++) {
        if (belong[bar[i]] != 0)
            ans = max(ans, dis[belong[bar[i]]]);
    }
    cout << ans;
    return 0;
}