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