差分约束系统

​ 差分约束系统是一种特殊的 $N$ 元一次不等式组。它包含 $N$ 个变量 $X_1$~$X_N$ 以及 $M$ 个约束条件，每个约束条件都是由两个变量作差构成的，形如 $X_i－X_j ≤ c_k$，，其中 $c_k$ 是常数（可以是非负数，也可以是负数），$1 ≤ i,j ≤ N,1 ≤ k ≤ M$。我们要解决的问题就是：

​ 求一组解 $X_1 = a_1,X_2 = a_2 ,…,X_N = a_N$，使所有约束条件都得到满足。

1：求不等式组的可行解：（建图转换为单源最短路问题）

​ 差分约束系统的每个约束条件 $X_i－X_j ≤ c_k$ 可以变形为 $X_i ≤ X_j + c_k$。这与单源最短路径问题中的三角形不等式 $dist[y] ≤ dist[x]+z$ 非常相似。因此，可以把每个变量 $X$；看作有向图中的一个节点 $i$，对于每个约束条件 $X_i－X_j ≤ c_k$,从节点 $j$ 向节点 $i$ 连一条长度为 $c_k$ 的有向边。

​ 注意到如果 $\{a_1,a_2, … ,a_N\}$ 是一组解，那么对任意的常数 $Δ$，${a1+Δ,…,a_N+Δ}$ 显然也是一组解(作差后 $Δ$ 恰好被消掉）所以,不妨先求一组负数解, 即假设 对于任意的 $i,X_i≤0$ ，然后再增加一个 $0$ 号节点，令 $X_0=0$。这样一来，就多了 $N$ 个形如 $X_i-X_0≤0$ 的约束条件，应该从节点 $0$ 向每个节点 $i$ 连一条长度为 $0$ 的有向边。

​ 设 $dist[0] = 0$，以$0$为起点求单源最短路。若图中存在负环，则给定的差分约束系统无解。否则， $X_i= dist[i]$ 就是差分约束系统的一组解。

综上：求一组可行解时。

• 将每个不等式 $X_i≤X_j+c_k$ 转换成一条从 $X_j$ 走到 $X_i$ ，长度为 $c_k$ 的边。
• 找一个源点：该源点必须可以走到所有边。
• 从源点开始求一遍单源最短路。若图中存在负环，则无解。

​ 在某些题目中，约束条件形如 $X_i - X_j≥c_k$。我们仍然可以从 $j$ 到 $i$ 连长度为 $c_k$ 的有向边，只是改为计算单源最长路，若图中有正环则无解。当然，我们也可以把约束条件转化成 $X_j－X_i≤－c_k$，再按照单源最短路进行计算。

2：如何求可行解的最大值和最小值 （这里的最值是指每变量的最值）

• 如果求得是 最大值（下确界），则应该求最短路。
• 如果求得时 最小值（上确界）（至少），则应该求最长路。

做题时应特别注意题目中的隐含条件（不等式）