差数约分

差分约束

笔记对应的视频
注意 仅当作自己日后用来复习的笔记
差分约束系统是下面这种形式的多元一次不等式组

（每个不等式称为一个约束条件，都是两个未知量之差小于或等于某个常数）

在算法竞赛中，很多题目会给出（或隐性地给出）一系列的不等关系，我们可以尝试把它们转化为差分约束系统来解决。

适用范围

1. 求不等式的可行解
2. 求最大值或最小值

1. 求不等式的可行解

方程 $x_{i} \le x_{j} + c_{k}$ 可以看成 $x_{j} \rightarrow x_{i}$ 边长为 $c_{k}$ 的一条边

每一个差分问题都可以转换为一个单源最短路问题: 将每一个不等式组转换成一条边, 然后求任意一个点的单源最短路求完以后, 则必然满足所有的限制条件

注意:

• 源点应该满足: 从源点出发, 可以走到所有的边

求解的步骤

1. 先将每个不等式 $x_{i} \le x_{j} + c_{k}$ 变成一条从 $x_{j}$ 到 $x_{i}$ 长度为 $c_{k}$ 的一条边
2. 找一个点, 使得该源点一定可以遍历到所有的边
3. 从源点求一遍单源最短路
   1. 若存在负环, 则原不等式组一定无解
   2. 如果无负环, 则 dist[i] 就是原不等式组的一个可行解

若图存在负环, 那么这个不等式组是矛盾的 (无解)

2.求最小值或者最大值 (每个变量的最值)

​如果求的是最小值, 则应该求最长路; 如果求的是最大值, 则求的是最短路
​
必有一个条件是大于或小于常数 ($x_{i} \le c$)

**$x_{i} \le c$ 的转化的方法

1. 建立一个超级源点, 例如 0 号点. 则可以转化为 $x_{i} \le x_{0} + c$ 即从 $0$ 到 $x_{i}$ 长度为 $c$ 的边

原理

以求 $x_{i}$ 的最大值为例, 求所有从 $x_{i}$ 出发, 构成不等式 $x_{i} \le x_{j} + c_{1} \le x_{k} + c_{2} + c_{1} \le … \le c_{1} + c_{2} +…$ 所计算出的上界. 最终 $x_{i}$ 的最大值等于所有上界的最小值

在图中, $x_{i}$ 的上界等价于从 $x_{0}$ 到 $x_{i}$ 的路径的最小值。