差分约束

简单记一下吧。

差分约束大致有两种建图方式：

• \(x \to y\) 表示 \(y\) 至少比 \(x\) 大 \(v\)。

此时符合 \(d_y \ge d_x + v\)。此时应该跑最长路，跑出来的结果为每个点最少是多少。（因为众多 \(\ge\) 的交要取最大的那个为“至少”）

• \(x \to y\) 表示 \(y\) 至少比 \(x\) 小 \(-v\)。

此时符合 \(d_y \le d_x + v\)。此时应该跑最短路，跑出来的结果为每个点最大是多少。（因为众多 \(\le\) 的交要去最小的那个为“至少”）

最好结合三个点（\(x \to y,y \to z,x \to z\)）的情况记忆。

差分约束

原文：https://www.cnblogs.com/JiaZP/p/13767572.html