【模板】差分約束 === >差分約束模板 > https://www.luogu.com.cn/problem/P5960 ## 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 太小時才會變大) ``` :::info 1. 確認不等式方向 xi-xj >= w or xi-xj <= w 2. 得出初始條件 ::: ###### tags: `競程` `模板` `圖論`