比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 xpb 运行时间 0.315 s
代码语言 C++ 内存使用 39.09 MiB
提交时间 2025-08-13 10:22:44
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;

vector<int> g[N], rg[N];
int c[N], id[N], sc[N];
bool b[N], sb[N];
int n, m, s, p;
stack<int> st;
bool v[N];
vector<int> sg[N];
int dp[N];

void d1(int u) {
    v[u] = 1;
    for (size_t i = 0; i < g[u].size(); ++i) {
        int vv = g[u][i];
        if (!v[vv]) d1(vv);
    }
    st.push(u);
}

void d2(int u, int x) {
    v[u] = 1;
    id[u] = x;
    sc[x] += c[u];
    for (size_t i = 0; i < rg[u].size(); ++i) {
        int vv = rg[u][i];
        if (!v[vv]) d2(vv, x);
    }
}

void kosaraju() {
    memset(v, 0, sizeof(v));
    for (int i = 1; i <= n; ++i)
        if (!v[i]) d1(i);
    memset(v, 0, sizeof(v));
    int x = 0;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (!v[u]) d2(u, x++);
    }
}

void build() {
    for (int u = 1; u <= n; ++u)
        for (size_t i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (id[u] != id[v])
                sg[id[u]].push_back(id[v]);
        }
}

int solve() {
    int st = id[s];
    dp[st] = sc[st];
    vector<int> ord;
    stack<pair<int, bool> > s;
    bool vt[N] = {0};
    for (int i = 0; i < N; ++i) {
        if (!vt[i] && !sg[i].empty()) {
            s.push(make_pair(i, 0));
            while (!s.empty()) {
                int u = s.top().first;
                bool p = s.top().second;
                s.pop();
                if (p) {
                    ord.push_back(u);
                    continue;
                }
                if (vt[u]) continue;
                vt[u] = 1;
                s.push(make_pair(u, 1));
                for (size_t j = 0; j < sg[u].size(); ++j) {
                    int v = sg[u][j];
                    if (!vt[v])
                        s.push(make_pair(v, 0));
                }
            }
        }
    }
    reverse(ord.begin(), ord.end());
    for (size_t i = 0; i < ord.size(); ++i) {
        int u = ord[i];
        if (!dp[u]) continue;
        for (size_t j = 0; j < sg[u].size(); ++j) {
            int v = sg[u][j];
            if (dp[v] < dp[u] + sc[v])
                dp[v] = dp[u] + sc[v];
        }
    }
    int res = 0;
    for (int i = 0; i < N; ++i)
        if (sb[i] && dp[i] > res)
            res = dp[i];
    return res;
}

int main() {
    freopen("atm.in","r",stdin);
    freopen("atm.out","w",stdout);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    cin >> s >> p;
    for (int i = 0; i < p; ++i) {
        int x;
        cin >> x;
        b[x] = 1;
    }
    kosaraju();
    for (int i = 1; i <= n; ++i)
        if (b[i]) sb[id[i]] = 1;
    build();
    cout << solve() << endl;
    return 0;
}