差分约束系统小结

介绍

首先差分约束系统是求解关于一组变量的特殊不等式组的方法，不等式组通常是以下形式：

$x_1 - x_5 \le -1$

$x_3 - x_4 \ge 3$

$x_2 - x_4 < 3$

$x1 - x2 = 9$

这里我们定义标准型为 $a_i - b_j \le c_k$ 这里 $c_k$ 为一个常量，a 和 b 是要求的变量。

上面的

$x_2 - x_4 < 3 \sim x_2 - x_4 \le 2$

$x1 - x2 = 9 \sim x_1 - x_2 \le 9 \And x_2 - x_1 \le -9$

都可以将上述等式化为标准型。

求解

现在的问题是怎么求解上述的不等式组。

我们首先看一下图论里面的单源最短路，假设 $dist[u]$ 为 u 到源点的距离。

那么如果有边$(u,v, w)$，从 u 到 v 并且距离为 w，那么我们可以把这条边当做一个约束条件，即对于最终答案的 $dist$ 数组，显然有 $dist[v] - dist[u] \le w$，然后我们将所有的边都转化为约束条件，那么最短路问题就可以转化为上面的差分约束系统，同样的差分约束系统系统也可以通过最短路来求解。

对于所有的 $a_i - b_j \le c_k$ 从 $b_j$ 向 $a_i$ 建一条费用为 $c_k$ 的边，然后跑最短路就是满足约束的答案了，如果有负环的话代表无解。

这里为了保证图连通，有时候需要建一个超级源点向所有点连一条费用为 0 的边。

需要注意的一点是，根据原题目写出约束条件的时候一定要保证不缺不漏，并且有的条件需要特判。

题集

相信大家都做过 POJ 的奶牛的那个经典差分约束系统的题，这里只推荐两个题目（都有坑点）：

http://acm.hdu.edu.cn/showproblem.php?pid=6252

https://vjudge.net/problem/UVALive-4885