差分约束系统
差分约束系统,是一类关于不等式组的线性规划问题。给定n个变量和m个形如xi−xj≤val(val已知)的不等式,要求出一组可行解或求出一组最小/大化 xt−xs(s,t给定)的解。
差分约束系统的转化
由于仅靠给定的约束条件很难在较快的速度内求解出希望的解,所以考虑将差分约束转化为其他模型。对给定的约束条件进行转化。 xi−xj≤val⇔xi≤xj+val⇔xj+val≥xi 最短路的转移判断条件为: disi+w(i,j)<disj 所以实际上最短路的计算就是尽量满足disi+w(i,j)≥disj的过程。于是考虑将差分约束转化为图论模型。将m个不等式转化为xi+val≥xj的形式,每个不等式等同于从点i向点j连一条权值为val的有向边来代表这条约束,然后在形成的图上使用最短路算法计算。
三角形不等式
下面我们考虑一个简单的例子。有下列三个不等式: B−A≤c C−B≤a C−A≤b 在满足以上约束条件的情况下求C−A的最大值。变换不等式得: A+c≥B B+a≥C A+b≥C 将第一个约束条件和第二个约束条件加起来得到: C−A≤a+c 转化为图论模型如下图: 可以发现同时满足C−A≤a+c与C−A≤b两个约束条件的C−A的最大值正好对应了图上从A到C的最短路:min(a+c,b)。这就是三角形不等式。将这种情况推广到拥有n个变量和m个不等式的情况,差分约束系统就变成了n个点m条边的最短路问题了。
差分约束系统的解
差分约束系统不一定有解,也不一定有有穷个解。
差分约束系统无解的情况即xt−xs不存在最大值,代表不等式间存在无法满足的关系,xt−xs≤val中的val可以为无限小。这种情况体现在图论模型中为无法求得最短路,即图中有负权环。
差分系统有无穷个解的情况即xt−xs的最大值可以是无穷大,代表xt与xs之间不存在约束关系。这种情况体现在图论模型中为s与t不连通。
对于这两种特殊的状况,题目一般会给出输出方式。差分约束系统的解有三种可能:无解,有穷个解,无穷个解。
差分约束系统的变形
如果仍然给定n个变量和m个不等式,但是要求xt−xs(s,t给定)的最小值。这时候就不能使用最短路算法来解决问题了。因为最短路算法只能求出xt−xs的最大值。我们仍然考虑三角形不等式。但是这次给定的不等式为xi−xj≥val(val已知)的形式: 由: B−A≥c C−B≥a C−A≥b 转化为: A+c≤B B+a≤C A+b≤C 将B−A≥c和C−B≥a加起来得到: C−A≥a+c 转化为图论模型如下图: 可以发现同时满足C−A≥a+c与C−A≥b两个约束条件的C−A的最小值正好对应了图上从A到C的最长路:max(a+c,b)。同上,这种情况也可以推广到拥有n个变量和m个不等式的情况,然后使用最长路算法解决。
不等式标准化
通过以上的变形,我们发现差分约束系统所给定的约束并不一定只有xi−xj≤val这一种形式。因为我们可以将不等式变形,所以给定的不等式的形式是无关紧要的。唯一需要关注的是题目的需求。如果题目要求将xt−xs最小化,那么使用最长路算法,要求xt−xs最大化则使用最短路算法。
还有,很多时候题目所给定的不等式带有大于号或小于号。在这种情况下,如果变量的取值范围在整数域,我们应该将其转化为大于等于或小于等于的形式。例如:A−B<c⇔A−B≤c−1