@[HMSF](/user/130483)
```cpp
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
// #define int long long
using namespace std;
inline int read()
{
int s = 0;
bool w = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
w = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
s = (s << 3) + (s << 1) + (ch ^ 48);
ch = getchar();
}
return w ? ~s + 1 : s;
}
const int _n = 10005;
const int _m = 100005;
const int inf = 2100000000;
struct edge
{
int v, next;
} e[_m][2];
int h[_n][2], w[_n], nw[_n], ec[2], n, m;
int dfn[_n], low[_n], times, cnt, mark[_n], ans, indeg[_n], dis[_n];
stack<int> st;
queue<int> q;
void adde(int u, int v, int op)
{
int ecnt = ++ec[op];
e[ecnt][op].v = v;
e[ecnt][op].next = h[u][op];
h[u][op] = ecnt;
return;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++times;
st.push(u);
for (int i = h[u][0]; i; i = e[i][0].next)
{
int v = e[i][0].v;
if (mark[v])
continue;
if (dfn[v] == 0)
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (!mark[v])
{
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u])
{
//cnt++;
++cnt;
while (true)
{
int x = st.top();
st.pop();
mark[x] = cnt;
nw[cnt] += w[x];
if (x == u)
break;
}
}
}
void path()
{
for (int i = 1; i <= cnt; ++i)
{
dis[i] = nw[i];
if (indeg[i] == 0)
q.push(i);
}
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = h[u][1]; i; i = e[i][1].next)
{
int v = e[i][1].v;
dis[v] = max(dis[v], dis[u] + nw[v]);
indeg[v]--;
if (!indeg[v])
q.push(v);
}
}
for (int i = 1; i <= cnt; ++i)
{
ans = max(ans, dis[i]);
}
return;
}
int main()
{
n = read();
m = read();
for (int i = 1; i <= n; ++i)
w[i] = read();
for (int i = 1; i <= m; ++i)
{
int u = read();
int v = read();
adde(u, v, 0);
}
for (int i = 1; i <= n; ++i)
{
if (!dfn[i])
tarjan(i);
}
for (int u = 1; u <= n; ++u)
{
for (int i = h[u][0]; i; i = e[i][0].next)
{
int v = e[i][0].v;
if (mark[u] != mark[v])
{
adde(mark[u], mark[v], 1);
//indeg[v]++;
indeg[mark[v]]++;
}
}
}
path();
printf("%d\n", ans);
// getchar();getchar();
return 0;
}
```
by metaphysis @ 2021-06-10 09:10:40