P5960 差分约束

原题

曾经会过

对于 \(x_i - x_j \leq k\) ，我们发现长得很像最短路/最长路的形式，因此我们可以抽象建图

建一个超级源点连向所有点，从超级原点跑最短路算法，跑出来的 \(dis_i\) 即对应 \(x_i\) 的一个解

前文提到过，差分约束问题可以转化为最短路或最长路问题，所以两种转化也就形成了两种不同的连边方法。

1. 连边后求最短路
   将 \(x_j - x_i \leq k\) 变形为 \(x_j \leq x_i + k\) ，即从 \(i\) 到 \(j\) 连一条边权为 \(k\) 的边。加入超级源点后求最短路，得到 \(x_i \leq 0\) 所有 \(x\) 最大解。
2. 连边后求最长路
   将 \(x_j - x_i \leq k\) 变形为 \(x_i \geq x_j - k\) ，即从 \(j\) 到 \(i\) 连一条边权为 \(-k\) 的边。加入超级源点后求最长路，得到 \(x_i \geq 0\) 所有 \(x\) 最小解。