@[Maysoul](/user/409774) 没用过SPFA求缩点，不过你这个
```
else if(staing[u]) low[u]=min(low[u],dfn[v]);
```
是不是应该是`staing[v]`。
by bzzltl @ 2023-07-04 20:00:26
在`tarjan`函数里面的。
by bzzltl @ 2023-07-04 20:00:51
@[bzzltl](/user/699852) 调完了，这个地方确实有锅……
而且下面缩点完之后存图的地方也写错了
by Maysoul @ 2023-07-04 20:35:51
@[Maysoul](/user/409774) 请问你写出来了没，我按照你的思路写了一次spfa，也只有40pts，如果你用spfa拿了满分，请发我一份看看。谢谢！
by blood_snow @ 2023-08-15 16:31:44
@[Maysoul](/user/409774)
```cpp/*
https://www.luogu.com.cn/problem/P3387
*/
#include <bits/stdc++.h>
#define chang(x) int(x.size())
#define PII pair<int,int>
#define fi first
#define ll long long
#define se second
using namespace std;
const int N = 1e5 +10;
int n,m;
int val[N];//存储每个节点的点权
int e[N],ne[N],w[N],h[N],idx = 0;
int ee[N],nee[N],ww[N],hh[N],idxx = 0;
int dfn[N] = {0},low[N],id[N],tim = 1;//dfn存储第一次被访问的时间点，low存储每个节点可以被儿子回溯的最小时间点,id记录每个节点隶属于哪个连通块
int stk[N],top = 0;//用数组模拟栈
bool in_stk[N];//该节点是否在栈中
int scc_cnt = 0;//强连通分量的数目
int dist[N];
int din[N],dout[N];//分别存储连通图里最大联通分量的入度和出度
vector<int>g[N];
bool vis[N];
queue<int> kong ;
void add(int a, int b)
{
e[idx] = b;
// w[idx] = val[b];
ne[idx] = h[a];
h[a] = idx ++;
}
int spfa(int s){
queue<int> q;
q = kong;
memset(vis,false,sizeof vis);
memset(dist,-0x3f,sizeof dist);
dist[s]=w[s];
q.push(s);
vis[s]=true;
int sum = 0;
while(q.size()){
int t = q.front();
vis[t] = false;
q.pop();
sum = max(sum, dist[t]);
for(auto x : g[t])
{
// dist[x] = max(dist[])
if(dist[x] < dist[t] + w[x])
{
dist[x] = dist[t] + w[x];
if(!vis[x])
{
q.push(x);
vis[x] = true;
}
}
}
}
return sum;
}
void tarjan(int x)
{
dfn[x] = low[x] = tim++;
stk[++top] = x, in_stk[x] = true;
for(int i = h[x]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[x] = min(low[j], low[x]);//例如b->c->d->b,b为(2,2),c为(3,3),此时x=d，由于d有一条通向b的点，所有会跳出，进行else if的判断后，d变为(4,2),然后通过上一层x=c的递归回溯让c变为(3,2)
}
else if(in_stk[j])
{
low[x] = min(low[x], low[j]);
}
}
if(dfn[x] == low[x])
{
scc_cnt ++;
int y;
while(1)
{
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
w[scc_cnt] += val[y];
if(y == x)break;
}
}
}
void solve()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1; i <= n; i ++)cin >> val[i];
for(int i = 1; i <= m; i ++)
{
int a,b;
cin >> a >> b;
add(a, b);
}
for(int i = 1; i <= n ; i ++)
{
if(!dfn[i])//这里必须遍历所有的点，如果外面加for直接tarjan（1）的话，会漏掉存在孤独点的情况，这里的题意里面只说了有向图，并不说明节点全部连通
{
tarjan(i);
}
}
for(int u = 1; u <= n; u ++)
{
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
int id1 = id[u], id2 = id[j];
if(id1 != id2)
{
// dout[id1] ++;//切记这里不写u，是连通块之间建边，而不是连通块内的节点
// din[id2] ++;//切记这里不能写j
g[id1].push_back(id2);
}
}
}
int ans = 0;
for(int i = 1; i <= scc_cnt ; i ++)
{
ans = max(spfa(i),ans);
}
cout << ans << endl;
}
int main()
{
solve();
return 0;
}
`````
by blood_snow @ 2023-08-15 16:53:44