求的是缩点之后图上的最长路,你只跑拓扑相当于求了全图权值和
by wzs_ @ 2019-11-19 18:20:54
@[金玉人品](/user/222675) 哦!!!! (拍大腿)
可是我的代码在3个测试点中只输出0是为什么呢?就是我确实是错了 , 所以我输出的答案应该比标答大 , 可实际我却输出0?
测试点1
```
10 20
970 369 910 889 470 106 658 659 916 964
3 2
3 6
3 4
9 5
8 3
5 8
9 1
9 7
9 8
7 5
3 7
7 8
1 7
10 2
1 10
4 8
2 6
3 1
3 5
8 5
```
正常输出:6911 ;
我的输出 0 ;
还望大佬帮忙看看 , 感激不尽 ,麻烦了
orz ;
by wocaicai @ 2019-11-19 21:38:27
```cpp
inline void tarjan( int u , int fa)
{
dfn[u] = low[u] = ++cloc ;
s.push(u) ;
for( int i = 0; i < g[u].size() ; i++)
{
register int nxx = g[u][i] ;
if( !dfn[nxx])
{
tarjan(nxx , fa) ;
low[u] = min( low[u] , low[nxx] ) ;
}
else if(!bccnum[nxx])low[u] = min( low[u] , dfn[nxx]) ; //这里
}
if( low[ u] == dfn[u])
{
bccnt++;
while(1){
int e = s.top() ;
s.pop() ;
bccnum[e] = bccnt;
sum[bccnt] += z[e] ;
if(e==u)
break ;
}
}
}
```
by wzs_ @ 2019-11-19 22:28:51
与它相连的点必须还没有出过栈,因为如果这个与它相连的点出过栈,但它没有出过栈,那么它们两个中间只有一条单向路,不构成强连通分量,所以不能更新
by wzs_ @ 2019-11-19 22:31:19
@[金玉人品](/user/222675) 谢谢谢谢 真的非常感谢!!!!
真的麻烦您了
orz ;
by wocaicai @ 2019-11-20 16:58:51