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
| #include <bits/stdc++.h>
using namespace std;
bool vis[10004];
int head[10004], cnt = 1, w[10004], sw[10004], i, n, m, u, v, dfn[10004], rt[10004], scecnt = 1, schead[10004], ncnt, aans[10004];
stack<int> stk;
struct Edge{
int from, to, next;
}e[100004], se[100004];
void getScc(int p) {
dfn[p] = rt[p] = ++ncnt;
vis[p] = true;
stk.push(p);
for (int k = head[p]; k; k = e[k].next) {
if (!dfn[e[k].to]) {
getScc(e[k].to);
rt[p] = min(rt[p], rt[e[k].to]);
}
else if (vis[e[k].to]) {
rt[p] = min(rt[p], rt[e[k].to]);
}
}
if (rt[p] == dfn[p]) {
while (stk.top() != p) {
rt[stk.top()] = dfn[p];
vis[stk.top()] = false;
sw[rt[p]] += w[stk.top()];
stk.pop();
}
vis[p] = false;
sw[rt[p]] += w[p];
stk.pop();
}
}
void getSccgraph() {
for (int k = 1; k <= m; ++k) {
if (rt[e[k].from] != rt[e[k].to]) {
se[scecnt].to = rt[e[k].to];
se[scecnt].next = schead[rt[e[k].from]];
schead[rt[e[k].from]] = scecnt++;
}
}
}
int dfs(int p) {
if (vis[p]) {
return aans[p];
}
vis[p] = true;
if (!schead[p]) {
return aans[p] = sw[p];
}
int ans = 0;
for (int k = schead[p]; k; k = se[k].next) {
ans = max(ans, dfs(se[k].to) + sw[p]);
}
return aans[p] = ans;
}
int main() {
cin >> n >> m;
for (i = 1; i <= n; ++i) {
cin >> w[i];
}
for (i = 1; i <= m; ++i) {
cin >> u >> v;
e[cnt].from = u;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt++;
}
for (i = 1; i <= n; ++i) {
if (!dfn[i]) {
getScc(i);
}
}
getSccgraph();
int realans = 0;
for (i = 1; i <= n; ++i) {
if (dfn[i] == rt[i]) {
realans = max(realans, dfs(rt[i]));
}
}
cout << realans << endl;
}
|