超级源点思路求助!!!
查看原帖
超级源点思路求助!!!
586417
Bz_nnn楼主2023/9/3 13:25

先引用oiWiki的一段话:

“如果需要判断整个图上是否存在负环,最严谨的做法是建立一个超级源点,向图上每个节点连一条权值为 0 的边,然后以超级源点为起点执行 Bellman–Ford(spfa) 算法。”

可是翻了翻题解,发现没有用超级源点的方法,自己写的时候发现:把节点0设为超级源点,但是如果把节点0-节点i的边权初始化为0,则发现当边权为负时答案不正确。如果把边权初始化为-inf,则发现当边权为正时答案不正确。

各位大佬有没有解决方法?万分感谢qwq

2023/9/3 13:25
加载中...