差分约束
-
差分约束是一种特殊的
\large N 元一次不等式组。它包含\large N 个变量以及\large M 个约束条件，每个约束条件都是由两个变量作差构成的。形如：\Large X_i - X_j \le c_k ，其中
\large c_k 是常数（可以是非负数，也可以是负数），\large 1 \le i,j \le N ，\large 1 \le k \le M 我们要解决的问题就是：求一组解
\Large X_1 = a_1,X_2 = a_2,\dots,X_N = a_N ，使得所有的约束条件都得到满足。
-
\Large X_i - X_j \le c_k \Large \Rightarrow \Large X_i \le X_j + c_k 这与单源最短路中的三角不等式
\Large dis[y] \le dis[x] + z 十分相似。
因此，可以把每个变量
\large X_i 看作有向图中的一个节点\large i ，对于每个约束条件\Large X_i - X_j \le c_k 从节点
\large j 向节点\large i 连一条长度为\large c_k 的有向边。 -
注意到如果
\large {a_1,a_2,\dots,a_N} 是一组解，那么对于任意的常数\Delta ，\large {a_1 + \Delta},\dots,a_N + \Delta 显然也是一组解(作差后\Delta 恰好被消掉)。所以不妨先求一组负数解，然后再增加一个0号节点，令\large X_0 = 0 ，这样一来，就多了\large N 个形如\Large X_i - X_0 \le 0 的约束条件，应该从0号节点向每个节点
\large i 连一条长度为0的有向边。 -
设
\large dis[0] = 0 ，以0为起点求单源最短路。若图中存在负环，则给定的差分约束系统无解。否则，\large X_i = dis[i] 就是差分约束系统的一组解。 -
在某些题目中，约束条件形如
\Large X_i - X_j \ge c_k 我们仍然可以从
\large j 到\large i 连一条长度为\large c_k 的有向边，只是改为计算单源最长路，若图中有正环也无解。当然也可以把约束条件改为\Large X_j - X_i \ge -c_k 再按照单源最短路进行计算。