差分约束
问题形式
解 $n$ 元一次不等式组，每个不等式形如 $x_i-x_j\le k$。
- 求是否有解
- 给定解的上/下限，求最大/最小解
方法
用最短路的性质（$(u,v,w)\in G\Rightarrow \operatorname{dis}_v\le\operatorname{dis}_u+w$）保证解符合方程（最长路同理）。
- 最大解问题转化为最短路，最小解问题转化为最长路。
- 将不等式转化为最短路/最长路性质的形式，建边。
- 建立源点，向每个节点连出一条长为上/下限的边。
- 求单源最短路/最长路，结果就是不等式组的最大/最小解
如果只要求判定是否有解，3、4 步删去，用 SPFA 判定是否有负环/正环。
典例
[SCOI2011] 糖果
因为建完图之后任意边的边权非负，所以一个环内出现正权极为无解，强连通分量缩点后拓扑排序求最长路。