这是我的代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
vector<int> G[N], H[N];
int ans, f[N], n, m, dfn[N], low[N], qlt[N], idx, vis[N], num, val[N], w[N], in[N];
stack<int> st;
void tarjan(int x){
st.push(x);
low[x] = dfn[x] = ++ idx;
vis[x] = 1;
for(auto i : G[x]){
if(!dfn[i]){
tarjan(i);
low[x] = min(low[x], low[i]);
}else if(vis[i]){
low[x] = min(low[x], dfn[i]);
}
}
if(low[x] == dfn[x]){
num ++;
int v;
do{
v = st.top();
st.pop();
qlt[v] = num;
val[num] += w[v];
vis[v] = 0;
}while(x != v);
}
}
void topo(){
queue<int> q;
for(int i = 1; i <= num; i ++){
if(in[i] == 0){
q.push(i);
f[i] = val[i];
}
}
while(!q.empty()){
auto x = q.front();
q.pop();
for(auto i : H[x]){
f[i] = f[x] + val[i];//<-----这里
in[i] --;
if(in[i] == 0){
q.push(i);
}
}
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> w[i];
}
while(m --){
int u, v;
cin >> u >> v;
G[u].push_back(v);
}
for(int i = 1; i <= n; i ++){
if(!dfn[i])tarjan(i);
}
for(int i = 1; i <= n; i ++){
for(auto j : G[i]){
if(qlt[i] == qlt[j])continue;
H[qlt[i]].push_back(qlt[j]);
in[qlt[j]] ++;
}
}
topo();
for(int i = 1; i <= num; i ++){
ans = max(ans, f[i]);
}
cout << ans;
return 0;
}
可以看到我指的那个地方没写 max 但他也过了。