模板及讲解

差分约束是什么

差分约束就是给出一些形如$x-y \ge c$的约束，问你是否有解，或求最大、最小解。该问题可以转化为图上最短路问题。

差分约束的几种形式

求最大差

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

求最小差

建立形如 $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$

负环无解，$dis=INF$为无限远，$dis[i]=min(a[i]-a[0])$

常见题型：

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