```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 10005, M = 100005;
int n, m;
int a[N];
int head[N], ver[M], nxt[M], cnt;
int stk[N], top;
int belong[N], tot;
int dp[N];
int dfn[N], low[N], tim;
bool vis[N];
int val[N], sum;
int _head[N], _ver[M], _nxt[M], _cnt;
int in[N];
void add(int u, int v) {
ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}
void _add(int u, int v) {
_ver[++_cnt] = v, _nxt[_cnt] = _head[u], _head[u] = _cnt;
}
void tarjan(int u) {
dfn[u] = low[u] = ++tim, stk[++top] = u, sum += a[u], vis[u] = 1;
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++tot;
do {
vis[stk[top]] = 0;
belong[stk[top]] = tot;
val[tot] = sum;
--top;
} while (stk[top + 1] ^ u);
sum = 0;
}
return;
}
void topsort() {
queue<int> q;
for (int i = 1; i <= tot; ++i) if (!in[i]) q.push(i), dp[i] = val[i];
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = _head[u]; i; i = _nxt[i]) {
int v = _ver[i]; --in[v];
if (!in[v]) q.push(v);
dp[v] = max(dp[v], dp[u] + val[v]);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i) {
int u, v; scanf("%d%d", &u, &v);
add(u, v);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) tarjan(i);
}
for (int i = 1; i <= n; ++i) {
for (int j = head[i]; j; j = nxt[j]) {
int v = ver[j];
if (belong[i] ^ belong[v]) _add(belong[i], belong[v]), ++in[belong[v]];
}
}
topsort();
int ans = 0;
for (int i = 1; i <= tot; ++i) ans = max(ans, dp[i]);
printf("%d", ans);
return 0;
}
```
代码放二楼
by Kobe303 @ 2022-02-15 10:47:29
我有一个 counter test
```plain
input:
4 3
1 1 1 1
1 2
3 4
4 2
output:
4
answer:
3
```
我再看看问题在哪
by devans @ 2022-02-15 10:53:55
@[siXYZit](/user/199139) 嗯谢谢
by Kobe303 @ 2022-02-15 10:57:12
我觉得 `val` 有问题
by devans @ 2022-02-15 11:08:01
@[siXYZit](/user/199139) 我也觉得
by Kobe303 @ 2022-02-15 11:08:39
@[siXYZit](/user/199139) 我刚才输出了一下 val 发现不对
by Kobe303 @ 2022-02-15 11:09:10
你要不别再 `tarjan` 里面弄 `val`，直接在外面弄 `val[belong[i]]+=a[i]` 这样
by devans @ 2022-02-15 11:09:35
@[siXYZit](/user/199139) 嗯我试试
by Kobe303 @ 2022-02-15 11:10:12
@[siXYZit](/user/199139) 过了蟹蟹
by Kobe303 @ 2022-02-15 11:11:52
@[siXYZit](/user/199139) 但是为什么我原来的写法无法正确处理 ```val``` 呢？
by Kobe303 @ 2022-02-15 11:12:23