差分约束 | DDOSvoid's Blog

简介

大概就是我有一堆形如 $x_i-x_j\le k$ 的约束

然后我要求是否存在合法解，或者求某元素的最小最大值一类的

对于 $x_i-x_j\le k$ 的限制，我们移项后得到 $x_i\le x_j+k$，我们建一条从 $j$ 到 $i$ 长度为 $k$ 的边

那么从 $j$ 到 $i$ 的最短路 $dis[j][i]$ 所表示的就是在满足所有限制的情况下 $x_i-x_j\le dis[j][i]$，也就是说 $x_i-x_j$ 的最大值就是 $dis[i][j]$

我们建一个源点 $s$，向每一个点连一条长度为 $0$ 的边，表示一个附加条件 $x_i\le s$

然后对于整张图跑最短路，如果不存在负环即有存在一组合法解

对于最小值，我们只需要将所有符号都转换成小于号然后跑最短路

最大值只需要将所有符号转换成大于号然后跑最长路

如果需要求范围的话，只需要求一次最长路和最短路

这样就能得到 $x_i-s\in [l,r]$，需要注意的是，在求最短路和最长路的两次操作中，$s$ 与 $x_i$ 的连边需要按照预设的 $s$ 的值来更改