【模板】差分約束

差分約束模板題

Solution

1. \(x_i - x_j \leq w\)

xi - xj <= w
xi <= xj+w
若 xj 已知，則 xi 必須要被縮小至至少 xj+w 以符合不等式
可以視作最短路中 relax 的過程

2. \(x_i-x_j \geq w\)

xi - xj >= w
xi >= xj + w
如果 xi < xj+w 則 relax (最長路)

3. 同時存在 \(x_i - x_j \leq w\) 和 \(x_p - x_q \geq w\)

xp - xq >= w
xq - xp <= -w

4. \(x_i - x_j = w\)

同時符合
xi-xj <= w
xi-xj >= w

5. 初始假設

1. xi-xj <= w, 得到最大解，假設 xi <= 0, 得到 xi-0<=0，由原點 0 連向 xi 邊權為 0
2. xi-xj >= w, 得到最小解，假設 xi >= 0, 得到 xi-0>=0，由原點 0 連向 xi 邊權為 0

6. 無解

建出來的圖存在負環，會重複更新 (永遠無法滿足條件)

性質

xi-xj <= w 做最短路，並且得到最大解 (xi 太大時才會變小)

xi-xj >= w 做最長路，並且得到最小解 (xi 太小時才會變大)

1. 確認不等式方向 xi-xj >= w or xi-xj <= w
2. 得出初始條件