```cpp
#include <iostream>
#include <queue>
#define INF 0x3f3f3f
using namespace std;
struct ln {
int u, v, nxt;
} a[50010], p[50010];
int n, m, r, ta, b;
int dfn[5010], prc[5010], h2d[5010], l2nsz, anstot, anslist[5010], f[5010],
chu[5010], ru[5010], colsz[5010], col[5010], stck[5010], stcktt, low[5010],
lnsz, hd[5010], tot, colcnt, mx, mxcl;
int sscpr[5010];
bool vis[50010];
void add(int u, int v) {
a[++lnsz].u = u;
a[lnsz].v = v;
a[lnsz].nxt = hd[u];
hd[u] = lnsz;
}
void add2(int u, int v) {
p[++l2nsz].u = u;
p[l2nsz].v = v;
p[l2nsz].nxt = h2d[u];
h2d[u] = l2nsz;
ru[v]++;
}
queue<int> q;
void tarjan(int u) {
dfn[u] = low[u] = ++tot;
stck[++stcktt] = u;
vis[u]=true;
for (int i = hd[u]; i; i = a[i].nxt) {
int v = a[i].v;
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]) {
int k;
while(k = stck[stcktt--]) {
col[k] = u;
vis[k]=false;
if(u==k)break;
sscpr[col[u]] += prc[k];
}
}
}
int topsort() {
for (int i = 1; i <= n; i++)
if (col[i]==i&&!ru[i]){
q.push(i);
anslist[i] = sscpr[i];
}
int te;
while (!q.empty()) {
te = q.front();
q.pop();
for (int i = h2d[te]; i; i = p[i].nxt) {
#define T p[i].v
anslist[T] = max(anslist[T], anslist[te] + sscpr[col[T]]);
ru[T]--;
if (!ru[T]) q.push(T);
#undef T
}
}
anstot=0;
for (int i = 1; i <= n; i++) anstot = max(anstot, anslist[i]);
return anstot;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> prc[i];
}
for (int i = 1; i <= m; i++) {
cin >> ta >> b;
add(ta, b);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= m; i++) {
if (col[a[i].u] != col[a[i].v]) {
add2(a[i].u, a[i].v);
}
}
cout << topsort() << endl;
return 0;
}
/*
10 20
970 369 910 889 470 106 658 659 916 964
3 2
3 6
3 4
9 5
8 3
5 8
9 1
9 7
9 8
7 5
3 7
7 8
1 7
10 2
1 10
4 8
2 6
3 1
3 5
8 5
6911
*/
```
by _TLEer_的小号 @ 2021-01-13 13:41:29
对于 $100\%$ 的数据，$1\le n \le 10^4,1\le m \le 10^5$，点权 $\in [0,1000]$
看清楚！
by lichenghan @ 2021-04-06 16:14:00
@[_TLEer_的小号](/user/362101)
```cpp
#include <iostream>
#include <queue>
#define INF 0x3f3f3f
using namespace std;
//
const int MAXN = 10010, MAXE = 100010;
struct ln
{
int u, v, nxt;
} a[MAXE], p[MAXE];
int n, m, r, ta, b;
int dfn[MAXN], prc[MAXN], h2d[MAXN], l2nsz, anstot, anslist[MAXN], f[MAXN],
chu[MAXN], ru[MAXN], colsz[MAXN], col[MAXN], stck[MAXN], stcktt, low[MAXN],
lnsz, hd[MAXN], tot, colcnt, mx, mxcl;
int sscpr[MAXN];
bool vis[MAXN];
void add(int u, int v)
{
a[++lnsz].u = u;
a[lnsz].v = v;
a[lnsz].nxt = hd[u];
hd[u] = lnsz;
}
void add2(int u, int v)
{
p[++l2nsz].u = u;
p[l2nsz].v = v;
p[l2nsz].nxt = h2d[u];
h2d[u] = l2nsz;
ru[v]++;
}
queue<int> q;
void tarjan(int u)
{
dfn[u] = low[u] = ++tot;
stck[++stcktt] = u;
vis[u] = true;
for (int i = hd[u]; i; i = a[i].nxt)
{
int v = a[i].v;
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])
{
int k;
while (k = stck[stcktt--])
{
col[k] = u;
vis[k] = false;
//if (u == k)
// break;
//sscpr[col[u]] += prc[k];
sscpr[u] += prc[k];
if (u == k) break;
}
}
}
int topsort()
{
for (int i = 1; i <= n; i++)
if (col[i] == i && !ru[i])
{
q.push(i);
anslist[i] = sscpr[i];
}
int te;
while (!q.empty())
{
te = q.front();
q.pop();
for (int i = h2d[te]; i; i = p[i].nxt)
{
#define T p[i].v
anslist[T] = max(anslist[T], anslist[te] + sscpr[col[T]]);
ru[T]--;
if (!ru[T])
q.push(T);
#undef T
}
}
anstot = 0;
for (int i = 1; i <= n; i++)
anstot = max(anstot, anslist[i]);
return anstot;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> prc[i];
}
for (int i = 1; i <= m; i++)
{
cin >> ta >> b;
add(ta, b);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= m; i++)
{
if (col[a[i].u] != col[a[i].v])
{
//add2(a[i].u, a[i].v);
add2(col[a[i].u], col[a[i].v]);
}
}
cout << topsort() << endl;
return 0;
}
```
by metaphysis @ 2021-06-10 09:32:37
@[metaphysis](/user/333388)
谢谢！
by _TLEer_的小号 @ 2021-06-11 22:56:57