差分约束

差分约束：所解决的问题给定很多不等式组形如 $x_i\le x_j+c_{k}x\_i\; \backslash leq\; x\_j\; +\; c\_k$，找到 $xx$ 的可行解。

1. 对于每个不等式$x_i{x}_j+c_{k}x\_i\; x\_j\; +\; c\_k$ 都转化成一条从 $x_{j}x\_j$ 走到 $x_{i}x\_i$ 边权为 $c_{k}c\_k$，

2. 然后找一个源点 （对于这个点必选能够走到所有边），跑一边最短路（最长路）算法。

3. 1. 最短路：对于 $j\to ij\; \backslash to\; i$ 求之前，$d[i]>d[j]+cd[i]\; >\; d[j]\; +\; c$。求之后，$d[i]\le d[j]+cd[i]\; \backslash leq\; d[j]\; +\; c$;

   • 一个图里每个点求完最短距离后每个点的最短距离都有第二个不等式满足

   • 即 任何一个最短路问题 可以 转化为一个差分约束问题

   • 同理 一个差分约束问题 可以 转化为一个单源最短路问题

   2. 最长路：对于 $j\to ij\; \backslash to\; i$ 求之前，。求之后，$d[i]\ge d[j]+cd[i]\; \backslash geq\; d[j]\; +\; c$;

4. 无解情况：

   • 假设存在一个负环，既有
   • 也就是 $x_2\le x_1+c1,x_1\le x_k+c_k,\mathrm{.}\mathrm{.}\mathrm{.},x_3\le x_2+c_{2}x\_2\; \backslash leq\; x\_1\; +\; c1,\; x\_1\; \backslash leq\; x\_k\; +\; c\_k,\; ...,\; x\_3\; \backslash leq\; x\_2\; +\; c\_2$
   • 所以 $x_2\le x_1+c_1\le x_k+c_1+c_k\le \mathrm{.}\mathrm{.}\mathrm{.}\le x_2+Cx\_2\; \backslash leq\; x\_1\; +\; c\_1\; \backslash leq\; x\_k\; +\; c\_1\; +\; c\_k\; \backslash leq\; ...\; \backslash leq\; x\_2\; +\; C$
   • 又因为
   • 所以就有矛盾
   • 综上，对于最短路存在负环，差分约束为题也就无解，同理对于最长路存在正环，差分约束为题也就无解。

5. 差分约束求可行解的最小值或者最大值

   • 结论：求最小值用最长路，求最大值用最短路。
   • 证明：以求最大值为例。对于每个 $x_i\le x_j+c_k\le \mathrm{.}\mathrm{.}\mathrm{.}\le x_0+Cx\_i\; \backslash leq\; x\_j\; +\; c\_k\; \backslash leq\; ...\; \backslash leq\; x\_0\; +\; C$，对于 $x_i\le x_0+Cx\_i\; \backslash leq\; x\_0\; +\; C$ 有多个不等式，其中右边是常数（$x_{0}x\_0$ 表示源点，一般初始值是一个常数），也就是x_i <= x_0 + C 都成立，x_i 一定是小于等于所有常数中的最小值，$x_0+Cx\_0\; +\; C$ 表示的就是从 $00$ 走到 $ii$ 的距离，也就对应求短源最短的最小值。