0x65 负环与差分约束

负环

给定一张有向图（无向图的每条边可以看作两条方向相反的有向边，从而按照有向图处理），每条边都有一个权值（长度）。若一条边的权值是负数，则称它是负权边。若图中存在一个环，环上各边的权值之和是负数，则称这个环为“负环”。

在0x61节中，我们介绍了多种求解单源最短路径问题的算法。这里，我们再次回顾它们的适用条件：

如果图中存在负环，那么直观表现为：无论经过多少轮迭代，总存在有向边 $(x, y, z)$ ，使得 $dist[y] > dist[x] + z$ ，Bellman-Ford 与 SPFA 算法永远不能结束。

根据抽屉原理，若存在一个 $dist[x]$ ，从起点1到节点 $x$ 的最短路包含 $\geq n$ 条边，则这条路径必然重复经过了某个节点 $p$ 。换言之，这条最短路径上存在一个环，环上各点都能更新下一个点的 $dist$ 值。 $p$ 绕这个环一圈，最终能更新它自己。因此，这个环的总长度是负数。每绕一圈，最短路长度只会越来越小，不可能收敛到每条边都满足三角形不等式的状态。基于这个结论，我们有以下的判定法则：

Bellman-Ford 判定负环

若经过 $n$ 轮迭代，算法仍未结束（仍有能产生更新的边），则图中存在负环。若 $n - 1$ 轮迭代之内，算法结束（所有边满足三角形不等式），则图中无负环。

SPFA判定负环

设 $cnt[x]$ 表示从1到 $x$ 的最短路径包含的边数， $cnt[1] = 0$ 。当执行更新 $dist[y] = dist[x] + z$ 时，同样更新 $cnt[y] = cnt[x] + 1$ 。此时若发现 $cnt[y] \geq n$ ，则图中有负环。若算法正常结束，则图中没有负环。

Bellman-Ford 判定负环的时间复杂度为 $O(nm)$ 。SPFA 判定负环稍快一些，但最坏情况下仍可能达到 $O(nm)$ 。

SPFA 判定负环的另一种方法是记录每个点入队的次数，次数达到 $n$ 时说明有负环。这种判定方法的效率一般不如我们上面提到的判定方法高，例如在 $n$ 个点构成一个负环的图中，上面提到的判定方法只要绕环一次，就能发现负环，而判定入队次数的做法需要绕环 $n$ 次。

当然，读者也可以同时使用这两种判定方法。甚至在某些题目中，我们可以根据运行时间限制，给队列的总长度（所有点入队总次数）设置一个上界，超出时直接判定存在负环。这样能保证算法不会超时，但可能会产生错误的判定（也就是我们常说的“卡时”做法）。

另外，还有其他优化手段，例如把SPFA的队列换成栈、把SPFA基于BFS改为基于DFS等。这些手段确实能提高负环存在时程序运行的效率，但有可能严重降低负环不存在时计算最短路的效率。读者应该谨慎使用。

【例题】Sightseeing Cows POJ3621

给定一张有向图，每个点都有一个权值 $\text{fun}[i]$ ，每条边有一个权值 $\text{time}[i]$ 。求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。输出这个最大值。

这是一道0/1分数规划问题，请读者回顾0x39节的内容。

二分答案。设二分的值为实数 $mid$ 。

对于一个由节点 $\{v_{1}, v_{2}, \dots, v_{t}\}$ 以及它们之间的有向边 $\{e_{1} = (v_{1}, v_{2}), \dots, e_{t} = (v_{t}, v_{1})\}$ 构成的环；为了叙述简便，我们把它记为 $S = (\{v_{i}\}, \{e_{i}\})$ 。

1. 如果图中存在一个环 $S$ ，使得 $\sum_{i=1}^{t} (mid * time[e_i] - fun[v_i]) < 0$ ，那么可知：

也就是说，本题所求的最大值一定大于 $mid$ 。

1. 如果对图中任意的环 $S$ ，都有 $\sum_{i=1}^{t}(mid * time[e_i] - fun[v_i]) \geq 0$ ，同理可知：

也就是说，本题所求的最大值不超过 $\text{mid}$ 。

综上所述，对于每轮二分，我们建立一张新图，结构与原图相同，但是没有点权，有向边 $e = (x, y)$ 的权值是 $\text{mid} * \text{time}[e] - \text{fun}[x]$ ，即本来的边权乘上 $\text{mid}$ 再减去入点的权值。

在这张新图上， $\sum_{i=1}^{t}(mid * time[e_i] - fun[v_i]) < 0$ 的含义就是图中存在负环。因此，我们用SPFA算法在新图上求最短路，若有负环，说明mid比答案小，应该令 $l = mid$ 。若最短路的求解正常结束，则令 $r = mid$ 。二分结束时就求出了本题的答案。

$\spadesuit$ 差分约束系统

差分约束系统是一种特殊的 $N$ 元一次不等式组。它包含 $N$ 个变量 $X_{1} \sim X_{N}$ 以及 $M$ 个约束条件，每个约束条件都是由两个变量作差构成的，形如 $X_{i} - X_{j} \leq c_{k}$ ，其中 $c_{k}$ 是常数（可以是非负数，也可以是负数）， $1 \leq i, j \leq N, 1 \leq k \leq M$ 。我们要解决的问题就是：求一组解 $X_{1} = a_{1}, X_{2} = a_{2}, \dots, X_{N} = a_{N}$ ，使所有约束条件都得到满足。

差分约束系统的每个约束条件 $X_{i} - X_{j}\leq c_{k}$ 可以变形为 $X_{i}\leq X_{j} + c_{k}$ 。这与单源最短路径问题中的三角形不等式dist[y]≤dist[x]+z非常相似。因此，可以把每个变量 $X_{i}$ 看作有向图中的一个节点 $i$ ，对于每个约束条件 $X_{i} - X_{j}\leq c_{k}$ ，从节点 $_j$ 向节点 $i$ 连一条长度为 $c_{k}$ 的有向边。

注意到如果 $\{a_{1}, a_{2}, \dots, a_{N}\}$ 是一组解，那么对任意的常数 $\Delta$ ， $\{a_{1} + \Delta, \dots, a_{N} + \Delta\}$ 显然也是一组解（作差后 $\Delta$ 恰好被消掉）。所以，不妨先求一组负数解，即假设 $\forall i, X_{i} \leq 0$ ，然后再增加一个0号节点，令 $X_{0} = 0$ 。这样一来，就多了 $N$ 个形如 $X_{i} - X_{0} \leq 0$ 的约束条件，应该从节点0向每个节点 $i$ 连一条长度为0的有向边。

设 $dist[0] = 0$ ，以0为起点求单源最短路。若图中存在负环，则给定的差分约束系统无解。否则， $X_{i} = dist[i]$ 就是差分约束系统的一组解。

在某些题目中，约束条件形如 $X_{i} - X_{j}\geq c_{k}$ 。我们仍然可以从 $j$ 到 $i$ 连长度为 $c_{k}$ 的有向边，只是改为计算单源最长路，若图中有正环则无解。当然，我们也可以把约束条件转化成 $X_{j} - X_{i}\leq -c_{k}$ ，再按照单源最短路进行计算。

【例题】Intervals POJ1201/TYVJ1415

给定 $n$ 个闭区间 $[a_i, b_i]$ （ $1 \leq i \leq n, 0 \leq a_i, b_i \leq 50000$ ）和 $n$ 个整数 $c_i$ （ $1 \leq i \leq n$ ）。你需要构造一个整数集合 $Z$ ，使得 $\forall i \in [1, n]$ ， $Z$ 中满足 $a_i \leq x \leq b_i$ 的整数 $x$ 不少于 $c_i$ 个。求这样的整数集合 $Z$ 最少包含多少个数。

本题的意思就是从 $0 \sim 50000$ 中选出尽量少的整数，使每个区间 $[a_i, b_i]$ 内都有至少 $c_i$ 个数被选。

设 $s[k]$ 表示 $0 \sim k$ 之间最少选出多少个整数。根据题意，有 $s[b_i] - s[a_i - 1] \geq$

$c_{i}$ 。这很明显是一个差分约束系统的模型。

不过，我们还要增加一些隐含的条件，才能保证求出的解是有意义的：

1. $s[k] - s[k - 1] \geq 0$ 。 $0 \sim k$ 之间选出的数肯定比 $0 \sim k - 1$ 多。

2. $s[k] - s[k - 1] \leq 1$ 。每个数只能被选一次。可变形为 $s[k - 1] - s[k] \geq -1$ 。

因此，我们把 $-1 \sim 50000$ 这 50002 个整数分别作为图中的节点，从每个 $k - 1$ 到 $k$ 连长度为 0 的有向边， $k$ 到 $k - 1$ 连长度为 $-1$ 的有向边，从每个 $a_i - 1$ 到 $b_i$ 连长度为 $c_i$ 的有向边。

最后，令 $s[-1] = 0$ ，以-1为起点求单源最长路。因为本题保证了 $c_{i}\leq b_{i} - a_{i} + 1$ ，所以图中没有正环，差分约束系统一定有解。求完最长路后， $s[50000] = dist[50000]$ 就是本题的答案。

本题也可以用贪心求解，并用数据结构进行优化。读者可以尝试思考一下。