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