差分约束

差分约束是用来解形如 $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)$。

需要注意的是，最短路求的是以起始点为基准的最大解，而最长路求的是以起始点为基准的最小解。