差分约束 学习笔记

模板及讲解
差分约束就是给出一些形如$x-y \ge c$的约束,问你是否有解,或求最大、最小解。

该问题可以转化为图上最短路问题。

1、求最大差
建立形如 $A-B \le C$ 的不等式,在原图中添加边 $B->A$ 边权为 $C$
对建好的图跑最短路,如果存在负环,无解(判断条件为某点被更新了$ n $次),$n $为图中点的数量

2、求最小差
建立形如 $A-B \ge C$ 的不等式,在原图中添加边 $B->A$ 边权为 $C$
对建好的图跑最长路,如果存在正环,无解(判断条件为某点被更新了$ n$ 次),$n$ 为图中点的数量

我们可以建立一个虚结点,然后让这个虚结点指向所有图中的结点,权值为0,从虚结点开始求最短路。(还可以先把所有点加入队列,之后dis全部初始化为0)

不等式标准化方法:
如果有一个不等式为$x-y>c$, 则可变为$x-y \ge c+1$
同理$x-y<c$可变为$x-y \le c-1$
如果是$x-y=c$,则变为两个式子$x-y\le c, x-y \ge c$

常见题型:
1、求最大差
Q:有若干约束,求最大差
解:见讲解
例题:hdu 3440
2、求最小差
Q:有若干约束,求最小差
解:见讲解
例题:poj 1201
3、求可行性
Q:有若干约束,求可行性
解:建立最小差/最大差无环/dis不等于INF即可
例题:hdu 3666
4、不等式标准化
Q:不等式为$x-y>c$
解:见讲解
例题:BZOJ 2330

------ 本文结束 ------