比赛 2025暑期集训第8场 评测结果 AWWWWWWWWW
题目名称 抢掠计划 最终得分 10
用户昵称 对立猫猫对立 运行时间 0.246 s
代码语言 C++ 内存使用 31.04 MiB
提交时间 2025-08-13 10:51:24
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const int INF = 1e9;
int n, m;
vector<int> adj[MAXN], radj[MAXN];
int cash[MAXN];
bool is_bar[MAXN] = {false};
int scc_id[MAXN], scc_cnt = 0;
int disc[MAXN], low[MAXN], time_cnt = 0;
bool on_stack[MAXN];
stack<int> st;
vector<int> scc_cash;
vector<bool> scc_has_bar;
vector<vector<pair<int, int>>> scc_adj;
void tarjan(int u) {
    disc[u] = low[u] = ++time_cnt;
    st.push(u);
    on_stack[u] = true;
    for (int v : adj[u]) {
        if (disc[v] == 0) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (disc[u] == low[u]) {
        scc_cash.push_back(0);
        scc_has_bar.push_back(false);
        scc_cnt++;
        while (true) {
            int v = st.top();
            st.pop();
            on_stack[v] = false;
            scc_id[v] = scc_cnt;
            scc_cash[scc_cnt] += cash[v];
            if (is_bar[v]) {
                scc_has_bar[scc_cnt] = true;
            }
            if (v == u) break;
        }
    }
}
void build_scc_dag() {
    scc_adj.resize(scc_cnt + 1);
    set<pair<int, int>> edges;
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            if (scc_id[u] != scc_id[v]) {
                edges.insert({scc_id[u], scc_id[v]});
            }
        }
    }
    for (auto [u, v] : edges) {
        scc_adj[u].push_back({v, scc_cash[v]});
    }
}
int spfa_longest_path(int start, const vector<vector<pair<int, int>>>& graph, const vector<bool>& has_bar) {
    vector<int> dist(graph.size(), -INF);
    vector<bool> in_queue(graph.size(), false);
    queue<int> q;
    dist[start] = scc_cash[start];
    q.push(start);
    in_queue[start] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (auto [v, weight] : graph[u]) {
            if (dist[v] < dist[u] + weight) {
                dist[v] = dist[u] + weight;
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    int max_cash = 0;
    for (int u = 1; u < graph.size(); ++u) {
        if (has_bar[u] && dist[u] > max_cash) {
            max_cash = dist[u];
        }
    }
    return max_cash;
}

int main() {
	freopen("atm.in", "r", stdin);
	freopen("atm.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> cash[i];
    }
    int bar_count, s;
    cin >> s >> bar_count;
    for (int i = 0; i < bar_count; ++i) {
        int x;
        cin >> x;
        is_bar[x] = true;
    }
    memset(disc, 0, sizeof(disc));
    memset(low, 0, sizeof(low));
    memset(on_stack, false, sizeof(on_stack));
    scc_cash.push_back(0);
    scc_has_bar.push_back(false);
    for (int u = 1; u <= n; ++u) {
        if (disc[u] == 0) {
            tarjan(u);
        }
    }
    build_scc_dag();
    int start_scc = scc_id[1];
    cout << spfa_longest_path(start_scc, scc_adj, scc_has_bar) << endl;
    return 0;
}