差分约束

差分约束系统是求解一组特殊的不等式组的方法。

差分约束举例

差分约束是有n个变量和m个不等式组成的。其中每个不等式都是形如:$x_i-x_j \leq b_k(i,j\in[1,n], k\in[1,m])$ 或 $x_i-x_j \geq b_k(i,j\in[1,n], k\in[1,m])$ 。

其中x为n个变量,b为m个不等式右边的值,用b的值来约束x的差称为差分约束。求一组解:$x_1=a_1,\quad x_2=a_2,\cdots x_n=a_n$使得所有约束条件(即m个不等式)均成立,则称差分约束有解,否则无解。

例如:
$$
(1)x_1-x_3 \leq 5;\quad
(2)x_3-x_5 \leq 4;\quad
$$
$$
(3)x_3-x_2 \leq 1;\quad
(4)x_1-x_5 \leq 10;\quad
(5)x_2-x_5 \leq 2;\quad
$$

观察$ x_1-x_5 $的关系,有如下三种关系:

  1. (4) $x_1-x_5 \leq 10$
  2. (1)+(2) $x_1-x_5 \leq 9$
  3. (1)+(3)+(5) $x_1-x_5 \leq 8 $

因为要满足所有等式的关系,所以取其中最大的3.$x_1-x_5 \leq 8$ 因为8一定小于9和10嘛,如果$x_1-x_5$小于等于8了,那他们一定小于等于9和10。

最短路问题

观察可发现 $x_i-x_j \leq b_k$ 可转换为:$x_i \leq b_k+x_j$ 。与求最短路公式中的dis[j]<dis[i]+w[i, j]非常相似,那差分约束问题是不是也可以转化成最短路问题来求解呢?肯定是可以的!先来看个例子:

img

仔细观察图中可发现总共有三条路径:

  1. 5 -> 1 长度为10
  2. 5 -> 3 -> 1 长度为9
  3. 5 -> 2 -> 3 -> 1 长度为8

很容易发现从5到1的最短路径是8。那为什么求差分约束问题能和最短路问题联系到一起呢?此处要先了解最短路知识,不懂的可以看一看我前面写的博客:1.dijkstra 2.SPFA 3.Floyd

差分约束和最短路问题

对于每个不等式$x_i-x_j \leq b_k$,我们都从结点j向结点i连一条长度为$b_k$的有向边。此时再看上面给出的那些不等式所转化成的图,是否和给出的图一样呢,最后求解的答案也一样。那么我们将差分约束问题转化成最短路问题,由最短路知识可知,当图中存在可达到的负环时,最短路一定无解。所以可以用SPFA来判断该差分约束问题是否有解。

这时候就有一个问题了,在最短路中有些点是不可达的,当遇到不可达的负环用SPFA一定判断不出来,但此时差分约束却是无解的。怎么办呢?有两种方法,其实本质都是一样的:

  1. 我们新定义一个结点,可以是$x_0$,让它向所有其它结点连一条边,让这些边的权值为0。因为SPFA是一个bfs的过程(有些题目需要把spfa改成dfs的形式,但是并不影响它访问的结点个数,只是访问顺序不一样),所以从这个结点出发一定能到达所有结点,而且不会影响结果的正确性。
  2. 第二种方法就比较暴力了,现在问题是有的结点访问不到怎么办,spfa又是求单源最短路,那我们直接一个for循环,每个结点都当一次源点,求n次单源最短路,这样就能访问到所有结点了。

两种方法的时间复杂度我不太会分析,但是感觉好像差不多一样的。

变化技巧

不等式转化

有时候题中会给出三种不等式,但是求最短路只能有一种不等式,这时候我们就可以把其他不等式变化成一样的不等式,进而转化成图。

题意 转化 连边
$x_i-x_j \leq b_k$ $x_i-x_j \leq b_k$ add(j, i, $b_k$)
$x_i-x_j \geq b_k $ $x_j-x_i \leq -b_k$ add(i, j, -$b_k$)
$x_i=x_j$ $x_i-x_j \leq 0$, $x_j-x_i \leq 0$ add(i, j, 0), add(j, i, 0)

最短路与最长路和差分约束的关系

有最短路了一定也有最长路,那他们和差分约束有什么关系呢?

当我们要求差分约束的最小值时,一定希望所有不等式都是大于等于号,这样求出来的一定是最小值。但是当我们有m个约束条件(即不等式),我们想要满足所有大于等于的不等式,我们一定得找到所有$ b_k $中最大的那一个,这样如果满足了最大的那个$ b_k $不等式,其他的大于等于不等式也一定都满足了。所以求$x_i-x_j$的最小值,就是求图中的最长路。所以,求最长路就是求差分约束中的最小值。求最长路的时候有正环则无解。

同理求最短路就是求差分约束的最大值。求最短路的时候有负环则无解。

什么?你问我最长路怎么求?把最短路算法中的小于号改成大于号不就行了。

例题

洛谷P1993

参考

  1. 夜深人静写算法(四)- 最短路和差分约束
  2. OI-WiKi(一个算法竞赛的百科)
  3. 维基百科:差分约束系统
  4. P1993小K的农场 题解
Donate comment here