检查过你的tarjan缩点没什么问题，但说实话不太清楚你那个SPFA在写什么，看似在跑SPFA，但实际上混入了什么入度，SPFA蛮跑不需要入度的啊？SPFA写法不应该是对每一个点跑一次最长路后取max吗。。。（离谱的是你似乎写的是跑最短路后取min？）总的而言这个SPFA我看得太迷糊了，提供一个拓扑排序加dp的写法吧，~~祝好~~
by 帝都_henry26268 @ 2023-11-07 16:51:25
@[Headofstate1945](/user/636409)
```cpp
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#define ll long long
using namespace std;
const int MAXN = 1e4+10;
const int MAXM = 1e5+10;
int n,m;
bool pd[MAXN][MAXN];
ll sum[MAXN];
int deg[MAXN];
queue<int> q;
int out[MAXN];
ll dp[MAXN];
ll pt[MAXN];
int col[MAXN],vis[MAXN];
int dfn[MAXN],low[MAXN];
stack<int> st;
int cnt=0,scc=0;
//原始(人)图
vector<int> vct[MAXN];
//缩点后新图
vector<int> e[MAXN];
//dp时顺序图，新图的反图
vector<int> dpe[MAXN];
void Tarjan(int u){
cnt++;dfn[u] = cnt;low[u] = cnt;
vis[u] = 1;st.push(u);
for(int i = 0;i < vct[u].size();i++){
int v = vct[u][i];
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u],low[v]);
}else if(vis[v]){
low[u] = min(low[u],dfn[v]);
}
}
if(dfn[u] == low[u]){
++scc;
//cout << u << " ";
int tp;
while(st.top() != u){
tp = st.top();st.pop();
col[tp] = scc;vis[tp] = 0;
sum[scc] += pt[tp];
//cout << tp << " ";
}
//cout << endl;
st.pop();
col[u] = scc;vis[u] = 0;
sum[scc] += pt[u];
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) scanf("%lld",&pt[i]);
for(int i = 1;i <= m;i++){
int u,v;scanf("%d%d",&u,&v);
vct[u].push_back(v);
//vct[v].push_back(u);
}
for(int i = 1;i <= n;i++){
if(!dfn[i])
Tarjan(i);
}
for(int u = 1;u <= n;u++){
for(int i = 0;i < vct[u].size();i++){
int v = vct[u][i];
if(col[u] != col[v] && !pd[col[u]][col[v]]){
//cout << col[u] << "-" << col[v] << endl;
pd[col[u]][col[v]] = true;
e[col[u]].push_back(col[v]);
deg[col[v]]++;
dpe[col[v]].push_back(col[u]);
}
}
}
//cout << scc << endl;
for(int i = 1;i <= scc;i++){
if(!deg[i])q.push(i);
}
int t = 0;
while(!q.empty()){
int u = q.front();
q.pop();out[++t] = u;
for(int i = 0;i < e[u].size();i++){
int v = e[u][i];
deg[v]--;
if(!deg[v])
q.push(v);
}
}
for(int i = 1;i <= scc;i++){
int now = out[i];
dp[now] = sum[now];
for(int j = 0;j < dpe[now].size();j++){
int lst = dpe[now][j];
dp[now] = max(dp[now],dp[lst] + sum[now]);
}
}
ll ans = 0;
for(int i = 1;i <= scc;i++){
ans = max(ans,dp[i]);
}
printf("%lld\n",ans);
return 0;
}
```
by 帝都_henry26268 @ 2023-11-07 16:52:16
@[帝都_henry26268](/user/315655) 感谢你的帮助
by Headofstate1945 @ 2023-11-09 10:29:11