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