---
# System prepended metadata

title: 【模板】差分約束
tags: [圖論, 競程, 模板]

---

【模板】差分約束
===

>差分約束模板
> 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: `競程` `模板` `圖論` 