负环

1344. Negative Cycle

给一个 \(n\) 个点 \(m\) 条边的有向图，边权可能为负。你需要判断图中是否存在负环。如果有，请输出任意一个负环。

限制：\(n \leq 2500, m \leq 6200, 0 \leq w_i \leq 10 ^ 9\)。

判定负环

存在负环的条件是什么？

存在一个点，在 Bellman-Ford 更新 \(n - 1\) 轮后还能继续更新。

如果你使用队列优化的 Bellman-Ford（有的地方也叫 SPFA），那么判定条件是 \(n\) 次出队：请注意，\(n\) 次更新并不一定意味着出现负环。

如果负环出现在了与 \(1\) 号点不连通的位置……

此时，我们不一定能够从 \(1\) 号点出发找到负环。

一个解决方法是，将所有点的初始距离设置为 \(0\)。

为什么这么做是对的？

• 你可以看做添加了一个 \(0\) 号点，向所有点连了边权为 \(0\) 的边，然后我们求的是 \(0\) 号点出发的最短路。由于 \(0\) 不会出现在任何环里，因此原图存在负环当且仅当新图存在负环。
• 在原图上，你也可以看做此时每个点的势能，表示每个点的从图里相对最高的「水平面」最长下滑的距离。存在负环的时候，势能不存在，或者受到负环影响的点等价于 \(-\infty\)。

找到负环

如果我们用上述方法成功判定存在负环，那么本题需要你输出一个解。

你可以通过记录每个点最后是被谁更新的，来从在第 \(n\) 轮被更新的点尝试复原一个负环。

在第 \(n\) 轮被更新的点为什么能够帮助找到负环？

考虑反证：往前 \(n\) 步内一定存在负环。

一个需要注意的点是：

在第 \(n\) 轮被更新的点一定在负环里吗？

不一定，考虑以下的形状：

graph LR
    id1 & id2 & id3 -->id4
    direction BT
    subgraph 负环
    id1((1))
    id2((2))
    id3((3))
    id1-->|-1|id2
    id2-->|-1|id3
    id3-->|-1|id1
    end
    subgraph 倒霉蛋
    id4((4))
    end

每一轮，倒霉蛋都会因为负环而更新，但并不在负环里。