1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include <bits/stdc++.h>
struct Edge {
int v;
};
using AdjList = std::vector<std::vector<Edge>>;
std::pair<int, std::vector<int>> scc(const AdjList& G) {
const int N = G.size();
std::vector<int> dfn(N, -1), low(N), scc_ids(N), stk;
stk.reserve(N);
int dfn_cnt = 0, scc_cnt = 0;
auto dfs = [&](auto& dfs, int u) -> void {
low[u] = dfn[u] = dfn_cnt++;
stk.push_back(u);
for (auto&& e : G[u]) {
if (dfn[e.v] == -1) {
dfs(dfs, e.v);
low[u] = std::min(low[u], low[e.v]);
} else {
low[u] = std::min(low[u], dfn[e.v]);
}
}
if (dfn[u] == low[u]) {
for (;;) {
int v = stk.back();
stk.pop_back();
dfn[v] = N;
scc_ids[v] = scc_cnt;
if (v == u) break;
}
++scc_cnt;
}
};
for (int u = 0; u < G.size(); ++u)
if (dfn[u] == -1) dfs(dfs, u);
return {scc_cnt, scc_ids};
}
std::vector<int> toposort(const AdjList& G) {
const int N = G.size();
std::vector<int> indeg(N);
for (int u = 0; u < N; ++u)
for (auto&& e : G[u]) ++indeg[e.v];
std::vector<int> ord;
ord.reserve(N);
std::queue<int> q;
for (int u = 0; u < N; ++u)
if (!indeg[u]) q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
ord.push_back(u);
for (auto&& e : G[u])
if (!--indeg[e.v]) q.push(e.v);
}
return ord;
}
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, M;
cin >> N >> M;
vector<int> a(N);
for (auto& x : a) cin >> x;
AdjList G(N);
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
G[u].emplace_back(Edge{v});
}
auto [scc_cnt, scc_ids] = scc(G);
AdjList G2(scc_cnt);
vector<int> a2(scc_cnt);
for (int u = 0; u < N; ++u) {
a2[scc_ids[u]] += a[u];
for (auto&& e : G[u])
if (scc_ids[u] != scc_ids[e.v]) G2[scc_ids[u]].emplace_back(Edge{scc_ids[e.v]});
}
auto topo = toposort(G2);
for (auto&& u : views::reverse(topo)) {
if (G2[u].empty()) continue;
auto v = G2[u] | views::transform([&](auto&& e) { return a2[e.v]; });
a2[u] += *ranges::max_element(v);
}
cout << *ranges::max_element(a2);
return 0;
}
|