差分约束
什么是差分约束?
是一种特殊的n元一次不等式组,它包含n个变量x1,x2,…,xn以及m个
约束条件
,每个约束条件是由两个其中的变量做差
构成的。
形如xi−xj≤ck,其中 1≤i,j≤n,i≠j,1≤k≤m并且ck是常数(可正可负)。
约束条件可以变形
xi−xj≤ck⇔xi≤xj+ck
这就很像图论中的求最短路不等式
dist[y]≤dist[x]+z
因此,我们可以把每个变量xi看做图中的一个结点
,对于每个约束条件xi−xj≤ck,看作从结点j向结点i连一条长度为ck的有向边。
如果{a1,a2,…,an}是该差分约束系统的一组解,那么对于任意常数d,{a1+d,a2+d,…,an+d}显然也是该差分约束系统的一组解,因为这样做差后d会被消掉。
设dist[0]=0并向每一个点连一条权重为0的边,跑单源最短路,若途中存在负环,则给定的差分约束系统无解,否则,xi=dist[i]为该差分约束系统的一组解。
差分约束最难的地方在于找不等关系
有什么用?怎么用?
一、求不等式组的可行解
源点需要满足的条件:从
源点
出发,一定可以走到所有的边
求一组解x1=a1,x2=a2,…,xn=an,使得所有的约束条件
得到满足,否则判断出无解。
步骤:
1. 先将每个不等式xi≤xj+ck,转换成一条从xj走到xi,长度为ck的边。
2. 找到一个超级源点
,使得该源点一定可以走到所以边
3. 从源点求一遍单源最短路
结果1:如果存在负环
,则原不等式组一定无解
结果2:如果没有负环
,则dist[i]就是原不等式组的一个可行解
二、如何求最大值
或者最小值
,这里的最值指的是每个变量的最值
结论:如果求的是最小值
,则应该求最长路
;如果求的是最大值
,则应该求最短路
问题1:如何转换xi≤c,其中c是一个常数,此类的不等式
方法:建立一个超级源点0
,然后建立0 -> i
的边,长度是c
的边即可
以求xi的最大值为例:
所有从xi出发,构成的不等式链
xi≤xj+c1≤xk+c2+c1≤…≤x0+c1+c2+…+cm(x0=0)
所计算出的上界
,最终xi的最大值等于所有上界的最小值
。
{x1≤5 x1≤7 x1≤9
如这个例子中,x1的最大值为5
转换为图论问题,就是求dist[i]的最小值
,即最短路求解
求xi的最小值
时则相反,通过不等式链计算出下界,最终在所有下界中取最大值
转换为图论问题就是求dist[i]得最大值,即最长路求解
参考文献:
OI Wiki差分约束