差分约束系统（Difference Constraints System）
题目描述
给定一组形如 \(x_j - x_i \le b_k\) 的不等式约束，其中 \(b_k\) 是一个常数（可为正、负或零），\(x_i, x_j\) 是变量。要求判断是否存在一组实数解满足所有约束，如果存在，则找出一组可行解。
输入：
- 约束个数 \(m\)，变量个数 \(n\)（变量通常编号为 \(x_1, x_2, \dots, x_n\)）。
- 每个约束：三个整数 \(i, j, b\)，表示 \(x_j - x_i \le b\)。
输出：
- 若存在可行解，输出一组解（通常要求所有解非负，或满足 \(x_i \ge 0\)）。
- 若不存在，报告无解。
解题思路
差分约束系统可以转化为图论中的单源最短路径问题来求解。
核心思想：
不等式 \(x_j - x_i \le b\) 可以改写为 \(x_j \le x_i + b\)，这与最短路径中的三角不等式 \(dist[j] \le dist[i] + w(i, j)\) 形式相同。
因此，我们可以构造一个有向图，以变量为顶点，每个约束对应一条从 \(i\) 到 \(j\) 的边，权值为 \(b\)。
构造图模型
- 顶点：每个变量 \(x_1, x_2, \dots, x_n\) 对应一个顶点。
- 边：对于约束 \(x_j - x_i \le b\)，添加一条从 \(i\) 到 \(j\) 的有向边，权值为 \(b\)。
- 超级源点：为了能够从单一源点出发计算最短路径，通常添加一个额外的顶点 \(x_0\)，并从 \(x_0\) 向所有其他顶点 \(x_i\) 连一条权值为 0 的边（即 \(x_i - x_0 \le 0\) 或 \(x_i \le x_0 + 0\)）。
这实际上等价于设定 \(x_0 = 0\)，并允许所有 \(x_i \le 0\)？
等一下——这里需要仔细推敲。
如何保证所有变量有下界？
通常我们要求 \(x_i \ge 0\)，这可以通过添加约束 \(x_i - x_0 \ge 0\) 来实现。
但我们的标准形式是 \(x_j - x_i \le b\)，所以不等式 \(x_i \ge 0\) 改写为 \(x_0 - x_i \le 0\)（因为 \(x_i \ge 0\) 等价于 \(-x_i \le 0\)，即 \(x_0 - x_i \le 0\) 如果我们设 \(x_0 = 0\)）。
更常见的做法是：直接添加一个超级源点 \(s\)，并添加边 \(s \rightarrow i\) 权值为 0，表示 \(x_i \le x_s + 0\)，但这样只能得到上界关系。
实际上，更通用的方法是：
若要求 \(x_i \ge c\)（例如 \(c = 0\)），则改写为 \(x_s - x_i \le -c\)，即从 \(i\) 到 \(s\) 的边权为 \(-c\)？
这样容易混淆。我们换一种更清晰的方式：
标准转化方法
约束形式：
(1) \(x_j - x_i \le b\) ⟹ 边 \(i \rightarrow j\) 权值为 \(b\)。
为了得到一组可行解，我们定义 \(dist[i]\) 为从源点 \(s\) 到 \(i\) 的最短路径长度。
在最短路径问题中，对于任意边 \(i \rightarrow j\) 权值 \(w\)，有 \(dist[j] \le dist[i] + w\)。
将 \(dist[i]\) 看作 \(x_i\)，则上述不等式正好是 \(x_j \le x_i + w\)，与原约束一致。
因此，我们只需添加一个超级源点 \(s\)，并添加边 \(s \rightarrow i\) 权值为 0（即 \(x_i \le x_s + 0\)），然后以 \(s\) 为源点求最短路径。
如果图中存在负权环，则最短路径无界（可以无限小），对应差分约束系统无解。
为什么？
因为若存在环 \(i_1 \rightarrow i_2 \rightarrow \dots \rightarrow i_k \rightarrow i_1\) 总权值 \(< 0\)，则沿环一圈约束叠加会得到 \(0 \le\) 负数，矛盾。
算法步骤
-
建图：
- 顶点：\(0, 1, 2, \dots, n\)（其中 0 是超级源点）。
- 对每个约束 \(x_j - x_i \le b\)：加边 \(i \rightarrow j\) 权值 \(b\)。
- 对每个变量 \(x_i\)（\(i = 1..n\)）：加边 \(0 \rightarrow i\) 权值 0（保证连通性，并隐含 \(x_i \le x_0 + 0\)）。
-
以顶点 0 为源点，运行 Bellman-Ford 算法（因为可能有负权边）。
- 若 Bellman-Ford 检测到负环 → 无解。
- 若无负环，则 \(dist[1..n]\) 就是一组可行解（\(x_i = dist[i]\)）。
-
解的范围：
注意这样得到的解中，\(x_0 = dist[0] = 0\)，且由于 \(0 \rightarrow i\) 权为 0，有 \(x_i \le 0\)。
但我们可能希望解是非负的，可以在得到解后整体加上一个常数（例如令 \(x_i' = x_i - \min_{j} x_j\)），因为差分约束系统允许整体平移。
举例说明
假设有以下约束（变量 \(x_1, x_2, x_3\)）：
- \(x_2 - x_1 \le 3\) （边 1→2 权 3）
- \(x_3 - x_2 \le -2\) （边 2→3 权 -2）
- \(x_1 - x_3 \le 1\) （边 3→1 权 1）
- \(x_1 \ge 0, x_2 \ge 0, x_3 \ge 0\)（即 \(x_1 - x_0 \ge 0\) 等，转化为 \(x_0 - x_1 \le 0\) 等等，但这里我们不这样做，而是直接加超级源点边权 0 并在最后平移）
建图（先不加非负约束）：
- 顶点 0,1,2,3
- 边：
- 0→1 权 0
- 0→2 权 0
- 0→3 权 0
- 1→2 权 3
- 2→3 权 -2
- 3→1 权 1
运行 Bellman-Ford：
从 dist = [0, ∞, ∞, ∞] 开始。
迭代过程略，最终 dist = [0, -2, 1, -1]（一组可行解）。
检查约束：
- \(x_2 - x_1 = 1 - (-2) = 3 \le 3\) ✔
- \(x_3 - x_2 = -1 - 1 = -2 \le -2\) ✔
- \(x_1 - x_3 = -2 - (-1) = -1 \le 1\) ✔
为了让解非负，令 \(m = \min\{-2, 1, -1\} = -2\)，每个值减去 m：
\(x_1' = 0, x_2' = 3, x_3' = 1\)，也是一组解。
时间复杂度
- 顶点数 \(n+1\)，边数 \(m+n\)。
- Bellman-Ford 复杂度 \(O((n+1) \cdot (m+n))\) 即 \(O(n(m+n))\)。
- 通常 \(m\) 是约束数，与边数同阶，所以可简化为 \(O(nm)\)。
特殊约束的处理
-
相等约束 \(x_j - x_i = b\)
拆成两个不等式：
\(x_j - x_i \le b\) 且 \(x_i - x_j \le -b\)。 -
大于等于约束 \(x_j - x_i \ge b\)
转化为 \(x_i - x_j \le -b\)。 -
严格不等式 \(x_j - x_i < b\)
若所有变量为整数，可改为 \(x_j - x_i \le b-1\)。
关键点总结
- 差分约束系统 ⇔ 有向图的单源最短路径问题。
- 约束 \(x_j - x_i \le b\) ⇔ 边 \(i \rightarrow j\) 权值 \(b\)。
- 超级源点保证连通性，并作为计算起点。
- 若图中有负环，则无解；否则最短路径值即为一组解。
- 解可整体平移以满足非负等额外要求。