4. 差分约束系统
1.定义：
如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。求解差分约束系统，可以转化成图论的单源最短路径（或最长路径）问题。
2. 数形结合
若一个系统由 n 个变量和 m 个不等式组成，并且这 m 个不等式对应的系数矩阵中每一行有且仅有一个 1 或 -1 ，其它的都为 0，这样的系统称为差分约束（difference constraints）系统。例如：
观察 x [ i ] - x [ j ] <= a [ k ], 将 x [ j ] 移至不等号的右边，即 x [ i ] <= x [ j ] + a [ k ].再进行同等的形式变换 d [ u ] + w (u, v) >= d [ v ]. 这时候联想到 SPFA 的松弛操作：
if (d[u] + w(u, v) < d[v) { d[v] = d[u] + w(u, v); }
对比上面的两个不等式，发现两个不等式的不等号正好相反，但思考一下其实它们的逻辑是一致的，这是因为SPFA的松弛操作是在满足小于的情况下进行的松弛，最后力求达到 d [ u ] + w (u, v) >= d [ v ] 的效果。所以我们可以将每个不等式转化为图上的有向边。
对于每个不等式 x [ i ] - x [ j ] <= a [ k ], 从结点 j 到 i 建立一条 j -> i 的有向边，边的权值为 a [ k ], 求 x [ n - 1 ] - x [ 0 ] 的最大值就是求 0 -- n - 1 的最短路。
3. 解的存在性
在最短路的问题中，会出现负圈或者不可达的情况，所以在不等式转化到图上时也可能出现上述问题。如果路径中出现了负圈，则表示最短路无限小，即不存在最短路，那么 x [ t ] - x [ s ] <= T ， T 无限小， 那么 x [ t ] - x [ s ] 的最大值不存在。
如果是从起点 s 无法到达 t 的情况，则表明 x [ t ] 和 x [ s ] 之间并没有约束条件，这种情况下 x [ t ] - x[ s ] 的最大值是无限大，解有无穷个。
综上所述：差分约束系统的解有三种情况：有解， 有无穷多解，无解。
4. 最大值 --> 最小值
当我们把上面的不等式组中 “ <= ” 全部变为 " >= "， 则就变为求 0 -- n - 1 的最长路。
5. 不等式的标准化
首先统一不等号的方向，如果求最大值，将不等号全部变为 “ <= ”，建图后求最短路；
如果求最小值，将不等号全部变为 " >= "，建图后求最长路。
如果有形如 A - B = C 这样的等式，则将其转化为:
A - B >= C
A - B <= C
再将其中的一种不等号反向，建图即可。
如果变量都是定义在整数域上， 那么遇到 A - B < C 这样的不带等号的不等式， 我们需要将其转化为 “ <= ” 或 “ >= ”， 即 A - B <= C - 1。
6. 差分约束的经典应用
（1） 线性约束
线性约束一般是在一维空间中给出一些变量（一般是定义位置），然后告诉你某两个变量的约束关系求两个变量 a 和 b 的差值的最大值或最小值。
例题： N 个 人编号为 1 - N，并按照编号排成一列，任何两个人的位置不重合。给定一些约束条件：
X 组约束条件 Ax 和 Bx 的距离不大于 Cx 。
Y组约束条件 Ay 和 By 的距离不小于 Cy。
如果这样的排列存在，求1 - N 的最长可能距离，如果不存在输出 -1，如果无限长输出 -2.
令 d [ x ] 为第 x 个人的位置，根据题意有如下的约束条件：
对于X组，有d[ Bx ] - d[ Ax ] <= Cx；
对于Y组，有d[ By ] - d[ Ay ] >= Cy；
任意两人位置不重合，有 d[ x ] - d [ x - 1] >= 1
我们要求的是 d[ N ] - d[ 1 ] 的最大值，即表示为 d[ N ] - d[ 1 ] <= T. 将所有的不等式转化为 “ <= ” 的形式：
d[ Bx ] - d[ Ax ] <= Cx；
d[ Ay ] - d[ By ] <= -Cy；
d[ x - 1 ] - d[ x ] <= -1；
对于 d[ x ] - d[ y ] <= z ，令 z = w（x， y），那么有 d[ x ] <= d[ y ] + w(x, y) ,所以当 d[ x ] > d[ y ] + w(x, y)时，更新 d[ x ] 的值，这就对应了最短路的松弛操作，于是问题就转化成了求 1 到 N 的最短路。
对于所有不等式 d[ x ] - d[ y ] <= z，从 y 向 x 建立一条权值为 z 的有向边。然后从 1 出发，利用SPFA求到各个点的最短路，如果 1 到 N 不可达，说明最短路无限长； 如果某个点进入队列的次数 >= N 次，则必定存在负圈，即没有最短路，否则 最后的的 d[ N ] 就是最短路。
（2） 区间约束
例题： 给定 n 个整数闭区间 和 每个区间中至少有多少整数需要被选中，每个区间的范围为 [ a, b ]，（0 <= a <= b <= 50000） 并且至少 c 个点被选中， 求 [0, 50000] 中至少需要多少点被选中。例如 ： 3 6 2 表示[ 3, 6]区间里至少选择 2 个点，有C24种情况。
这类问题没有线性约束那么明显，需要将问题转化一下。考虑到最后需要求的是一个完整区间内至少有多少点被选中，我们试着用 d [ i ] 表示 [0, i]区间至少有多少点能被选中，显然 d[ - 1 ] = 0.对于每个区间描述，可以表示成 d[ b ] - d[ a ] >= c,即 d[ b ] >= d[ a ] + c, 而我们的目标是 d[ 50000 ] - d[ - 1 ] >= T 这个不等式中的 T，将所有区间描述转化成图后求 -1 到 50000 的最长路。
这里忽略了一些要素，因为 d[ i ] 描述了一个求和函数，所以对于 d[ i ] 和 d[ i - 1 ] 是有限制的。考虑到每个点都有选和不选两种情况，所以 d[ i ] 和 d[ i - 1 ] 需要满足 0 <= d[ i ] - d[i - 1] <= 1 （即第 i 个数是选或不选）。
这样一来，还需要加入 50000 * 2 = 100000 条边，由于数据较大需要用 SPFA 优化，由于 -1 不能映射到小标，所以可以将所有点右移一位。
（3） 未知条件约束
未知条件约束是指在不等式的右边不一定是一个常数，可能是个未知数，通过枚举这个未知数，然后对不等式转化为差分约束进行求解。
例题： 在一家超市里，每个时刻都需要有营业员看管， R(i) （0 <= i <= 24）表示从 i 时刻开始到 i + 1 时刻结束需要的营业员的数目，现在有 N 个人申请这项工作，并且每个申请者都有一个起始工作时间 ti ，如果第 i 个申请者被录用，那么他会连续工作 8 小时。现在要求选择一些申请者录用，使得任一时刻 i ，营业员数目都能 ≥ R（i）。
本篇学习自：夜深人静写算法（四） - 差分约束
