@[。VХ](/user/214649)
```cpp
#include<bits/stdc++.h>
using namespace std;
int dq[10005], ss[10005], tme, dfn[10005], low[10005], eq[10005], rd[10005], dp[10005], n, v[10005];
vector<int> a[10005], b[10005], xtd;
stack<int> qwq;
int find(int x)
{
if (ss[x] == 0 || ss[x] == x)
{
return ss[x] = x;
}
return find(ss[x]);
}
void dfs(int x)
{
tme++;
dfn[x] = low[x] = tme;
qwq.push(x);
v[x] = 1;
for (int i = 0; i < a[x].size(); i++)
{
if (!dfn[a[x][i]])
{
dfs(a[x][i]);
low[x] = min(low[x], low[a[x][i]]);
}
else
{
if (v[a[x][i]] == 1)
{
//low[x] = min(low[x], low[a[x][i]]);
//上述写法虽然不会产生错误的结果,但不是Tarjan算法的正确实现
low[x] = min(low[x], dfn[a[x][i]]);
}
}
}
if (dfn[x] == low[x])
{
while (v[x] != 2)
{
ss[find(qwq.top())] = find(x);
v[qwq.top()] = 2;
qwq.pop();
}
}
}
inline void xt()
{
for (int i = 1; i <= n; i++)
{
eq[find(ss[i])] += dq[i];
for (int j = 0; j < a[i].size(); j++)
{
if (find(ss[i]) != find(ss[a[i][j]]))
{
b[find(ss[i])].push_back(find(ss[a[i][j]]));
//rd[find(ss[i])]++;
rd[find(ss[a[i][j]])]++;
}
}
}
}
inline int tp()
{
queue<int> q;
int maxn = 0;
for (int i = 1; i <= n; i++)
{
if (!rd[i] && find(ss[i]) == i)
{
q.push(i);
dp[i] = eq[i];
}
}
while (q.size())
{
maxn = max(maxn, dp[q.front()]);
for (int i = 0; i < b[q.front()].size(); i++)
{
dp[b[q.front()][i]] = max(dp[b[q.front()][i]], dp[q.front()] + eq[b[q.front()][i]]);
rd[b[q.front()][i]]--;
if (!rd[b[q.front()][i]])
{
q.push(b[q.front()][i]);
}
}
q.pop();
}
return maxn;
}
int main()
{
int m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> dq[i];
}
while (m--)
{
int x, y;
cin >> x >> y;
a[x].push_back(y);
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
{
dfs(i);
}
}
xt();
cout << tp();
return 0;
}
```
by metaphysis @ 2021-06-10 09:55:29
@[metaphysis](/user/333388) 谢谢!!1
by Real_Create @ 2021-06-10 16:42:08