```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 20, M = 1e5 + 20;
ll n, m, a[N], x, y;
ll dfn[N], low[N], t;
ll val[N], to[N], tot = 0, in[N];
ll f[N], b[N], cnt = 0;
stack<ll> S;
bool flag[N];
vector<ll> G[N], New[N];
vector<ll> In[N], Out[N];
queue<ll> q;
void tarjan(ll u) {
dfn[u] = low[u] = ++t;
S.push(u);
flag[u] = 1;// 1
for(int i = 0; i < G[u].size(); i++) {
ll v = G[u][i];
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(flag[v] == 1) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
val[++tot] += a[u];
flag[u] = false;// 2
to[u] = tot;
while(!S.empty()&& S.top() != u) flag[S.top()] = 0, to[S.top()] = tot, val[tot] += a[S.top()], S.pop();
S.pop();
}
}
void TP() {
for(int i = 1; i <= tot; i++) {
if(in[i] == 0) q.push(i);
}
while(!q.empty()) {
ll u = q.front();
q.pop();
b[++cnt] = u;
for(int i = 0; i < New[u].size(); i++) {
ll v = New[u][i];
in[v] --;
if(in[v] == 0) q.push(v);
}
}
}
int main (){
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i <= m; i++) {
scanf("%lld%lld", &x, &y);
G[x].push_back(y);
}
for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i++) {
for(int j = 0; j < G[i].size(); j++) {
ll u = i, v = G[i][j];// 3
if(to[u] != to[v]) {
New[to[u]].push_back(to[v]);
// Out[u].push_back(v);
In[to[v]].push_back(to[u]);
in[to[v]] ++;// 4
}
}
}
TP();
ll maxx = 0;
for(int i = 1; i <= cnt; i++) {
ll v = b[i];
f[v] = val[v];
for(int j = 0; j < In[v].size(); i++) {
ll u = In[v][i];
f[v] = max(f[v], f[u] + val[v]);
}
maxx = max(f[v], maxx);
}
printf("%lld", maxx);
return 0;
}
```
前两个注释是tarjan的错误。
一个变量名错了
一个是强连通分量次序最小的点u最后pop掉了，但是flag没有标记u出栈。
第三个应该为G[i][j]便利原图的边
emmm，你的拓扑排序我一下子没懂，实际上是不用记录入边具体的点的，从度为0的点开始设个初始值给它出边的点转移就好了，然后出边的度数--。直到v点度数为0，放入队列
by yiyi049 @ 2023-10-17 21:31:17