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