差分约束系统（Difference Constraints System）原理与求解
差分约束系统是一种特殊的线性不等式组，它由形如 \(x_j - x_i \leq b_k\) 的约束条件组成，其中 \(b_k\) 是常数。这类系统在任务调度、时间安排、路径规划等问题中经常出现。我将带你逐步理解其原理、图论建模方法以及求解算法。
1. 问题描述
假设我们有 \(n\) 个变量 \(x_1, x_2, \dots, x_n\)，以及 \(m\) 个约束条件，每个约束都是两个变量的差值的上限约束：
\[x_j - x_i \leq b_k \]
其中 \(i, j\) 是变量下标，\(b_k\) 是实数（通常为整数）。目标是找到一组变量赋值 \(x_1, x_2, \dots, x_n\)，满足所有约束，或判断无解。
示例：
- 约束1: \(x_2 - x_1 \leq 3\)
- 约束2: \(x_3 - x_2 \leq -1\)
- 约束3: \(x_1 - x_3 \leq -2\)
问是否存在可行解。
2. 图论建模：转化为最短路问题
这是差分约束系统的核心技巧。我们将每个约束 \(x_j - x_i \leq b_k\) 转化为一条有向边：
- 从节点 \(i\) 到节点 \(j\) 连一条有向边，边权为 \(b_k\)。
为什么可以这样转化？
考虑最短路径的三角不等式：如果从 \(i\) 到 \(j\) 的最短路径长度为 \(dist[j]\)，那么对于任意边 \(i \to j\) 有权重 \(w\)，有：
\[dist[j] \leq dist[i] + w \]
移项得：
\[dist[j] - dist[i] \leq w \]
这正是约束 \(x_j - x_i \leq w\) 的形式。因此，如果我们以某个变量为基准（比如设 \(dist[0] = 0\)），那么 \(dist[1..n]\) 就可以作为 \(x_1..x_n\) 的一组可行解。
注意：系统必须有一个“参照点”，通常我们引入一个超级源点 \(s\)，从 \(s\) 向所有其他点连一条权值为 0 的边，表示 \(x_i - x_s \leq 0\)，即 \(x_i \leq 0\)（或根据问题调整）。另一种常见设定是令 \(x_s = 0\)，然后求解相对值。
3. 求解步骤
差分约束系统的求解可以统一为以下步骤：
步骤1：建图
- 创建 \(n+1\) 个节点（编号 0 到 \(n\)），其中节点 0 是超级源点。
- 对每个约束 \(x_j - x_i \leq b\)，添加有向边 \(i \to j\)，权重为 \(b\)。
- 从源点 0 向每个节点 \(i\) 添加有向边 \(0 \to i\)，权重为 0（表示 \(x_i \leq x_0 + 0\)，通常设 \(x_0=0\) 作为基准）。
步骤2：判断负环
- 从源点 0 开始，运行 Bellman-Ford 算法 或 SPFA 算法 求单源最短路径。
- 如果图中存在从源点可达的负权环，则差分约束系统无解。
- 原因：假设环上有 \(k\) 条边，对应约束：
\[ x_2 - x_1 \leq w_1,\quad x_3 - x_2 \leq w_2,\quad \dots,\quad x_1 - x_k \leq w_k \]
将这些不等式相加，左边抵消为 0，右边为环上权重和 $\sum w_i$。如果 $\sum w_i < 0$，则得到 $0 \leq \text{负数}$，矛盾，故无解。
- 如果没有负环，则最短路径值 \(dist[1..n]\) 就是一组可行解。
步骤3：获取解
- 令 \(x_i = dist[i]\) 即可。注意，由于最短路中 \(dist[0]=0\)，这组解满足 \(x_i \leq 0\)。如果需要非负解，可以对所有 \(x_i\) 加上同一个常数（因为不等式只关心差值）。
4. 完整示例求解
考虑前面的例子，变量 \(x_1, x_2, x_3\)：
- 约束：
- \(x_2 - x_1 \leq 3\) → 边 \(1 \to 2\)，权 3
- \(x_3 - x_2 \leq -1\) → 边 \(2 \to 3\)，权 -1
- \(x_1 - x_3 \leq -2\) → 边 \(3 \to 1\)，权 -2
- 添加超级源点 0，边 \(0 \to 1, 0 \to 2, 0 \to 3\) 权 0。
- 从 0 开始求最短路（Bellman-Ford）：
- 初始化 \(dist=[0,\infty,\infty,\infty]\)
- 松弛过程略，最终得到（例如）：
\[ dist=[0, -2, 1, 0] \]
即 $x_1=-2, x_2=1, x_3=0$
- 验证：
- \(x_2 - x_1 = 1 - (-2) = 3 \leq 3\) ✅
- \(x_3 - x_2 = 0 - 1 = -1 \leq -1\) ✅
- \(x_1 - x_3 = -2 - 0 = -2 \leq -2\) ✅
所有约束满足。
5. 其他形式的约束转换
- 如果约束是 \(x_j - x_i \geq b\)，两边乘以 -1 变为 \(x_i - x_j \leq -b\)。
- 如果约束是 \(x_j - x_i = b\)，可拆为两个不等式：
\[ x_j - x_i \leq b \quad \text{和} \quad x_j - x_i \geq b \]
后者转换为 \(x_i - x_j \leq -b\)。
- 如果要求变量非负（\(x_i \geq 0\)），可添加边 \(0 \to i\) 权 0（因为 \(x_i - x_0 \leq 0\) 且 \(x_0=0\) 时 \(x_i \leq 0\)，这不对！）。正确做法是：添加约束 \(x_i - x_0 \geq 0\) 即 \(x_0 - x_i \leq 0\)，即边 \(i \to 0\) 权 0（注意方向）。
6. 实际应用场景
- 任务调度：任务 i 必须在任务 j 开始后至少 \(b\) 时间才能开始 → \(start_j - start_i \geq b\)。
- 距离限制：在布局或规划中，两点坐标差不超过某值。
- 系统时钟同步：节点间时钟偏差范围约束。
7. 算法选择与复杂度
- 使用 Bellman-Ford：时间复杂度 \(O(n(m+n))\)，适合约束不多的情况。
- 使用 SPFA：实践中更快，但最坏仍为 \(O(nm)\)。
- 如果所有权重非负（即 \(b_k \geq 0\)），可使用 Dijkstra + 斐波那契堆 \(O(m + n\log n)\)，但差分约束一般允许负权。
8. 思考
为什么不用单纯形法解线性规划？因为差分约束是最短路问题的对偶形式，用图论算法更高效。另外，如果只需要判断可行性，等价于判断图中是否有负环，可用 SCC 缩点后分别检测（如 Johnson 算法中的做法）。
总结：差分约束系统通过约束不等式→有向边→最短路/负环检测的转化，将线性不等式求解转化为经典图论问题。掌握这一转换思想，就能灵活处理各类“差值限制”问题。