差分约束系统将一组形如 xⱼ - xᵢ ≤ c 的不等式转化为图上的最短路问题，用 Bellman-Ford 或 SPFA 判定可行性并求出一组解。
一、问题形式
Mermaid · 渲染中（下方为源码）
graph LR A[x_j - x_i <= c] --> B[建边 i->j 权 c] B --> C[Bellman-Ford 最短路] C --> D[有负环? 无解] C --> E[dist 即一组解]
给定 n 个变量 x₁, x₂, ..., xₙ 和 m 个约束：
xⱼ - xᵢ ≤ cₖ
问是否存在一组满足所有约束的解。
二、转化为最短路
约束 xⱼ - xᵢ ≤ c 等价于：
dist[j] ≤ dist[i] + c
这正是最短路松弛条件！因此：
- 从 i 向 j 连一条权为 c 的边
- 如果图有负环 → 无解
- 否则 dist[] 就是一组合法解
建图规则
| 约束 | 建边 |
|---|---|
| xⱼ - xᵢ ≤ c | i → j，权 c |
| xⱼ - xᵢ ≥ c | 转化为 xᵢ - xⱼ ≤ -c，j → i，权 -c |
| xⱼ = xᵢ | xⱼ-xᵢ≤0 且 xᵢ-xⱼ≤0 |
三、代码实现
// 差分约束：求 x[n] - x[1] 的最大值
// 约束：x[b] - x[a] <= c
public boolean solve(int n, int[][] constraints) {
// 建图
List<int[]>[] adj = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
for (int[] con : constraints) {
int a = con[0], b = con[1], c = con[2];
adj[a].add(new int[]{b, c}); // a → b, 权 c
}
// 超级源点 0 → 所有点，权 0（保证连通）
for (int i = 1; i <= n; i++) {
adj[0].add(new int[]{i, 0});
}
// Bellman-Ford / SPFA 判负环
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[0] = 0;
for (int round = 0; round <= n; round++) {
boolean updated = false;
for (int u = 0; u <= n; u++) {
if (dist[u] == Integer.MAX_VALUE / 2) continue;
for (int[] edge : adj[u]) {
int v = edge[0], w = edge[1];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
updated = true;
if (round == n) return false; // 负环 → 无解
}
}
}
if (!updated) break;
}
return true; // dist[] 是一组解
}