差分约束

求一组不等式的可行解

不等式必须是 这种形式才可以
类比最短路里的三角不等式，从j 到 i且边权为c，若dist[i] <= dist[j] + c可用j更新i。故可以通过单源最短路求解不等式的一个可行解
差分约束 等价于 单源最短路问题

源点怎么选？
从源点出发，一定可以直接或间接走到所有边。
求解步骤：

  1. 用不等式建图
  2. 找一个超级源点，使得该源点能遍历到所有边
  3. 源点处求单源最短路 
     1. 存在负环说明不等式组一定无解，这两者等价
     2. 没有负环，则`dist[i]`就是不等式组的一个可行解

求最大值/最小值

最值指每个变量的最值
求最值的题一定存在约束条件。类似于 这种形式

如何对这种不等式建边？
利用超级源点，0，建立0 -> i边权为c的边即可。
如何求一个最小的可行解/最大的可行解？

• 如果求最小值，应该求最长路（即满足所有不等式约束的最小值就是超级源点到每个变量对应的节点的最长路，即大于等于）
• 如果求最大值，应该求最短路（即满足所有不等式约束的最大值就是超级源点到每个变量对应的节点的最短路，即小于等于）

判断绝对关系是否存在

固定一点即可
最大距离用最短路
最小距离用最长路

例题

AcWing 1169. 糖果
AcWing 362. 区间 本题最难的是节点的含义如何表示。还有就是有负权边的话求最短路/最长路不能用Dijkstra
AcWing 1170. 排队布局 要求两点：求是否存在可行解，是否存在绝对关系（固定一点即可）
AcWing 393. 雇佣收银员 技巧：变量变成常量，再加上对应的约束