```cpp
#include <iostream>
#include <queue>
#include <vector>
const int MAXN{ 10000 + 5 };
const int MAXM{ 100000 + 5 };
typedef int NodeType;
typedef int EdgeType;
typedef long long DataType;
struct Edge
{
NodeType end;
EdgeType next;
};
Edge G[MAXM * 2]{}, newG[MAXM * 2]{};
NodeType head[MAXN]{}, newhead[MAXN]{};
EdgeType count{}, newcount{};
DataType value[MAXN]{};
NodeType dfn[MAXN]{}, low[MAXN]{}, dn{};
NodeType stack[MAXN]{}, top{};
NodeType group[MAXN]{};
EdgeType newcnt{};
DataType newval[MAXN]{};
bool visit[MAXN]{};
NodeType s[MAXM]{}, t[MAXM]{};
NodeType indegree[MAXN]{};
DataType dis[MAXN]{};
NodeType n{};
EdgeType m{};
void addedge(NodeType start, NodeType end, Edge *G, NodeType *head, int &count)
{
G[++count].end = end;
G[count].next = head[start];
head[start] = count;
}
void dfs(NodeType now = 1)
{
using std::min;
visit[now] = true;
stack[++top] = now;
dfn[now] = low[now] = ++dn; // 将 low[now] 初始化为 dn 不会导致错误, 且一般都这么写
for (int i{ head[now] }, end{}; i; i = G[i].next)
{
end = G[i].end;
if (!dfn[end]) //若为树边
{
dfs(end);
low[now] = min(low[now], low[end]); //因为儿子可能非割点，所以 low 可能会小
}
else if (visit[end]) low[now] = min(low[now], dfn[end]); //若不为树边，判断 visit 与否？
}
if (dfn[now] == low[now])
{
newcnt++;
do
{
group[stack[top]] = newcnt;
newval[newcnt] += value[stack[top]];
visit[stack[top--]] = false;
} while (now != stack[top + 1]);
}
}
DataType topo()
{
std::queue<NodeType> Q;
NodeType now{};
DataType ans{};
for (EdgeType i = 1; i <= newcnt; i++)
{
if (indegree[i] == 0)
{
Q.push(i);
dis[i] = newval[i];
}
}
while (Q.size())
{
now = Q.front();
Q.pop();
for (EdgeType i = newhead[now], end{}; i; i = newG[i].next)
{
end = newG[i].end;
dis[end] = std::max(dis[end], dis[now] + newval[end]);
indegree[end]--;
if (indegree[end] == 0) Q.push(end);
}
}
for (NodeType i = 1; i <= newcnt; i++) ans = std::max(ans, dis[i]);
return ans;
}
int main()
{
using namespace std;
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (NodeType i = 1; i <= n; i++) cin >> value[i];
for (EdgeType i{}; i < m; i++)
{
cin >> s[i] >> t[i];
addedge(s[i], t[i], G, head, count);
}
for (NodeType i = 1; i <= n; i++) if (!dfn[i]) dfs(i);
fill(head + 1, head + n + 1, 0);
::count = 0;
for (EdgeType i = 0; i < m; i++)
{
if (group[s[i]] != group[t[i]])
{
addedge(group[s[i]], group[t[i]], newG, newhead, newcount);
indegree[group[t[i]]]++;
}
}
cout << topo() << endl;
}
```
要注意开新数组存新边，入度存得也有问题，其他还有一些问题，请自己对比一下
by DAMDAM @ 2023-10-13 18:13:59
@[DAMDAM](/user/759326) 谢谢大哥qwq
我刚才调过了，数组不清没有太大影响（因为链式前向星只需要清head
主要是 topo 函数中压入队列的条件错了。
by InoriILU @ 2023-10-13 19:05:54