差分约束是用来解形如 \(x_{1}-x_{2}\leqslant k\) 的若干个方程的算法。
我们发现可以将方程移项成 \(x_{1}\leqslant x_{2}+k\),解方程的时候考虑建图,从 \(x_{2}\) 向 \(x_{1}\) 连一条长度为 \(k\) 的边,然后对这张图建一个超级源点,向所有点连一条长度为 \(0\) 的边,最后跑最短/最长路得出的 \(dis\) 就是每个变量的一个取值。
为什么这样做是对的呢?因为如果有一条 \(u\) 到 \(v\) 的长度为 \(w\) 的边,那么跑完最短路以后 \(dis_{v}\) 一定不大于 \(dis_{u} + w\),恰好满足一个方程。那么将所有边连上以后再跑最短路就可以满足所有方程,最长路同理。
另外,如果有负环则无解。
时间复杂度 \(\Theta(\rm SPFA)\)。
需要注意的是,最短路求的是以起始点为基准的最大解,而最长路求的是以起始点为基准的最小解。
