@[人林](/user/273468) 求最长路不能用dij，要用死了的spfa
by Belarus @ 2020-11-06 10:04:34
你的tarjan写错了8
by NuoCarter @ 2020-11-06 10:05:40
```cpp
for(int j=0;j<e[i].size();j++) {
int nex=e[i][j];
if(nex==i) continue;
if(!dfn[nex]) {
dfs(nex);
low[i]=min(low[nex],low[i]);
}
else low[i]=min(low[i],dfn[nex]);
}
```
这里不能写else，应该判断是否在栈中
by NuoCarter @ 2020-11-06 10:06:20
```cpp
inline void tarjan(int x){
dfn[x]=low[x]=++cnt;
sta[++siz]=x;vis[x]=true;
for(int i=head[x];i;i=Next[i]){
int y=to[i];
if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}
else if(vis[y]){low[x]=min(low[x],dfn[y]);}
}
if(dfn[x]==low[x]){
cntscc++;
belong[x]=cntscc;
fval[cntscc]+=val[x];
vis[x]=false;
while(sta[siz]!=x){
fval[cntscc]+=val[sta[siz]];
belong[sta[siz]]=cntscc;
vis[sta[siz--]]=false;
}
siz--;
}
}
```
by NuoCarter @ 2020-11-06 10:07:10
@[Belarus](/user/223392) 谢谢，但是为什么呢qwq
by YOKIMIYA @ 2020-11-06 10:09:44
@[人林](/user/273468) 最长路不满足Dijkstra三角形不等式的贪心规则
by Belarus @ 2020-11-06 10:11:08
@[NuoCarter](/user/67621) 那为什么要判断是否在栈内呢qwq
by YOKIMIYA @ 2020-11-06 10:19:39
@[Belarus](/user/223392) 噢噢噢噢明白了，谢谢大佬
by YOKIMIYA @ 2020-11-06 10:26:17
@[人林](/user/273468) low的定义是能够回溯到的最早已经在栈中的结点。。肯定要判断在不在栈中a。。你再看看缩点的讲解呢
by NuoCarter @ 2020-11-06 10:56:29
@[NuoCarter](/user/67621) 和我当初学的定义不太一样……我再去看看啦，谢谢大佬
by YOKIMIYA @ 2020-11-06 11:12:59