差分约束
2026-02-10
简介
如果一个题目给定了多个不等式关系,并且需要求最大/小值,那么大概率需要用到差分约束。
具体的来讲,我们可以将这些不等式关系转换为 xi≤xj+wk,根据图论中的三角形不等式,只需要指定一些值的大小就可以求出可行解,也就是说,一般的不等式只有相对关系。
若需要让 xi≤xj+wk,只需要连一条 j→i 的边,边权为 wk,由于 xi,xj,wk∈Z,我们可以将小于和大于转换为 −1 和 +1。
注意
在这其中,必须要保证所有点是可达的,如果存在不可达,则不满足三角形不等式。
一般可以使用超级源点处理,向所有点连一条边。
还有一个问题,求最小值要用最长路,求最大值要用最短路。
为什么呢?以求最小值为例,还记得我们固定的那个点吗?在更新中,如果使用最短路大概率会出现负数,而最长路则能保证最开始的点一定是最小值。
也可以理解为,我们要求的是 x1≥x2+w2≥x3+w3≥⋯≥xn+wn,而 x1 的下界则是所有约束条件中的上界。
处理完上述问题,还有一个问题
如果图中存在负环,证明什么?
这种情况下,令环上的一个点为 x1,剩下一直到 xi,编号小的点向编号大的点连边的边权为 w1∼wi,我们一定可以推出 x1≤x1+∑w1wi,而 ∑w1wi<0,所以三角形不等式不成立,也就是图中存在负环时表示不等式组无解。
例题
Acwing 1169. 糖果
Acwing 362. 区间
题目的范围是 1∼50000,但我们可以统一加一个 1,变成 1∼50001。
然后我们需要进行一个转换:设 si 表示从 1∼i 中选中的数的个数。
容易发现,我们有以下几个约束条件:
- si≥si−1
- si−1≥si−1
- 对于一个约束条件 [a,b] 和 c,sb≥sa−1+c
要求最小值,所以跑最长路即可。
Acwing 1170. 排队布局
读完题目,会发现我们还需要判断 1 和 n 的距离能否无限长,怎么办呢?
如果 1 到 n 的距离不是无限长,那么一定存在 t 使得 disn≤dis1+t,如果距离是无限长的,也就是说 ∄t 满足上述条件(也可以理解为不存在这条路径)。
我们先将相对距离转换一下,令 dis1=0,则 disn 就是它们之间的距离。
所以我们只需要规定 dis1=0,从 1 开始跑最短路,看看 disn 是不是 +∞ 即可。
Acwing 393. 雇佣收银员
与不等式有关,所以优先考虑不等式,令 xi 表示在时刻 i 选择的人数,可以列出如下几个不等式:
- 0≤xi≤numi
- xi−7+xi−6+⋯+xi≥ri
很明显,第二种并不符合差分约束的形式,考虑使用前缀和,令 si=∑xi,可以写成这样:
- 0≤si−si−1≤numi
- 当 i≥8 时,si−si−8≥ri
- 当 1≤i≤7 时,si+s24−si+16≥ri
好是好了,但是第三个咋办?那个 s24 没法处理啊!所以我们可以枚举 s24,将其直接赋值来进行更新。
