# 經典網路流問題 Classic Flow Problems
很多人都說 flow 是在通靈，其實不是這樣。當你認真讀過幾本圖論、演算法、線性規劃跟計算理論的書之後，flow 根本只是小菜一碟。這篇算是網路流這個主題的集大成，會涵蓋 (幾乎) 所有競程常見的網路流問題，我會幫大家梳理 flow 的知識點

本篇會假設前面你都會了，在閱讀這篇之前，建議先讀過前面幾篇 :

- [匹配與霍爾定理 Matching and Hall's Theorem](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)
- [Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)
- [擴充路徑演算法 Augmenting Path Algorithm](https://hackmd.io/@ShanC/Augmenting-Path-Algorithm)
- [匈牙利演算法 Hungarian Algorithm](https://hackmd.io/@ShanC/Hungarian-Algorithm)
- [連通性與 Menger 定理](https://hackmd.io/@ShanC/Menger-Theorem)
- [最大流量-最小割定理 Max-flow Min-cut Theorem](https://hackmd.io/@ShanC/maxflow-mincut-theorem)
- [二分圖匹配與網路流 Bipartite Matching and Flow](https://hackmd.io/@ShanC/bipartite-and-flow)
- [Edmonds-Karp 演算法與 Dinic 演算法](https://hackmd.io/@ShanC/Edmonds-Karp-and-Dinic)

## 問題化約 Problem Reduction
計算機最重要的任務就是解問題。我們生活周遭有非常多問題，有些可計算，有些不可計算，但那不是今天的重點。有時我們會好奇問題要怎麼計算出來，卻苦苦想不到辦法來處理問題，或許我們可以考慮 problem reduction

### 解題機器 Problem Solver
「解題機器」$M$ 是一台抽象的機器 (||其實我想講的是圖靈機，只是怕有人聽不懂||)，他可以代表一台計算機 (電腦)、一個程式或是一個演算法。一個可計算的問題通常是由實例 (instance) 與答案 (answer) 組成。$M$ 的作用就是可以把 instance 轉換成正確的 answer

<center>
<img src="https://hackmd.io/_uploads/rkUsoFCtex.png" style="margin: 0 auto; display: block; width: 400px">
</center>

但是在實務上，不是每個問題我們都可以找到相對應的 solver，所以可以考慮以下方法

### 化約 Reduction
把一個問題 $A$ 轉換成另一個問題 $B$ 來解，這樣如果已知 $B$ 問題的 solver $M$，我們就能間接解決原本的問題。這叫做 reduction，是我們在搞演算法一個最重要的手法。Reduction 本質上就是一台機器 $M'$，專門把 $A$ 的 instance 轉換成 $B$ 的 instance

<center>
<img src="https://hackmd.io/_uploads/HkFvTFCKgg.png" style="margin: 0 auto; display: block; width: 400px">
</center>

### 舉例說明
舉一些在國高中就會遇到的例子

<center>
<img src="https://hackmd.io/_uploads/Sk64z5Atle.png" style="margin: 0 auto; display: block; width: 400px">
</center>

### 最大流量問題化約圖
顯然問題互相轉換之下，也可以畫成一張龐大的圖。在這篇筆記中，我們會得到以下化約圖

<center>
<img src="https://hackmd.io/_uploads/BJ1NmaQcll.png" style="margin: 0 auto; display: block; width: 400px">
</center>

## 最大流量問題 Maximum Flow Problem

### 問題簡述
在流量網路 $N$ 中，從 $s$ 到 $t$ 的最大流量為多少呢?
||詳細定義我就不再講了，有興趣自己去[複習](https://hackmd.io/@ShanC/maxflow-mincut-theorem)||

<center>
<img src="https://hackmd.io/_uploads/rJceOqRFxe.png" style="margin: 0 auto; display: block; width: 400px">
</center>

### 解法
最大流量問題可以用[「Edmonds-Karp 演算法」或是「Dinic 演算法」](https://hackmd.io/@ShanC/Edmonds-Karp-and-Dinic)這兩種 solver 來解掉。這個問題可以說是本篇核心中的核心，所有的問題都會用**最大流量問題**的 solver 去解

### 最小割問題 Minimum Cut Problem
#### 問題簡述
在一張圖 $G$ 中，存在兩節點 $s, t\in V(G)$。請問要刪除多少邊才能使 $s$ 跟 $t$ 不連通?

#### Reduction
要注意，**一般圖 $G$ 與流量網路 $N$ 是不同的數學物件**，中間必須經過轉換，不可以直接拿來講，許多教學都忽略這點

- 若 $G$ 是無向圖，就把它會為有向圖 (雙向)

<center>
<img src="https://hackmd.io/_uploads/Hys7ZjRtxl.png" style="margin: 0 auto; display: block; width: 400px">
</center>

- 若 $G$ 是帶權邊的話，可以化為多重邊

<center>
<img src="https://hackmd.io/_uploads/HJFQHWbgll.png" style="margin: 0 auto; display: block; width: 400px">
</center>

將兩點之間的「多重邊數量」化為「同一條邊上面的容量」後，根據[「最大流量-最小割定理」](https://hackmd.io/@ShanC/maxflow-mincut-theorem) :

$$
\mathrm{最大流量}=\mathrm{最小割}
$$

<center>
<img src="https://hackmd.io/_uploads/Hyl_XX3skeg.png" style="margin: 0 auto; display: block; width:550px">
</center>

離開 $s$ 且流滿的邊無法形成 augmenting path，因此會形成最小割。如此一來，**最小割問題**就能夠化約成**最大流量問題**

### 小技巧 : 線性規劃
最大流問題的線性規劃可以寫作以下 :

$$
\begin{aligned}
\max\quad & \sum_{v\in V}f_{sv}-\sum_{v\in V}f_{vs}\\
\text{s.t.}\quad
&f_{uv}\leq c(u, v)\quad\forall u, v\in V\\
&\sum_{v\in V} f_{vu}-\sum_{v\in V} f_{uv}=0\quad\forall u\in V-\{s, t\}\quad\\
&f_{uv}\geq0\quad\forall u, v\in V
\end{aligned}
$$

有時候可以先把要最佳化的式子跟限制寫下來，幫助大腦整理資訊，然後去看看是否跟最大流問題很像，或許可以試試看。Dual 的東西我懶得寫，反正應該看得出來

## 最大互斥邊路徑問題 Maximum Disjoint Paths Problem
有時候我不加「邊」這個字，但其實都一樣
### 問題簡述
在一張圖 $G$ 中，存在兩節點 $s, t\in V(G)$。請問從 $s$ 到 $t$ 有幾條「邊」互不相同的路徑?

<center>
<img src="https://hackmd.io/_uploads/B1EvtoAtge.png" style="margin: 0 auto; display: block; width:550px">
</center>

### 解法 : 化約成最小割問題 Reduce to Min-cut Problem
根據 [Menger 定理](https://hackmd.io/@ShanC/Menger-Theorem) :

$$
\mathrm{最小 (邊) 割}=\mathrm{最大互斥邊路徑數量}
$$

<center>
<img src="https://hackmd.io/_uploads/SJDSosRYel.png" style="margin: 0 auto; display: block; width:550px">
</center>

如此一來，**最大互斥邊路徑問題的 instance** 就原封不動就可以轉化成**最小割問題的 instance**。如果要進一步化成流量網路的話，只要把容量都設為 $1$ 即可

### 點/邊
最大互斥邊路徑問題還有一個節點的版本叫作「最大互斥『點』路徑問題」，透過 [line graph](https://hackmd.io/@ShanC/Menger-Theorem#%E7%B7%9A%E5%9C%96-Line-Graph) $L(G)$，點的版本與邊的版本可以互相轉換，所以先把它們視為同一個問題

<center>
<img src="https://hackmd.io/_uploads/ByRSCpj3Jg.png" style="margin: 0 auto; display: block; width: 550px">
</center>

### 同時取最長遞增子序列問題
#### 問題簡述
給一個存在最常遞增子序列的序列 $S$。若在不允許重複取同一元素的情況下，把每個最常遞增子序列取出，則最多會取出多少個子序列呢?

<center>
<img src="https://hackmd.io/_uploads/ryE7dKz9ge.png" style="margin: 0 auto; display: block; width: 500px">
</center>

如上圖，最多可以取出 $2$ 個最長遞增子序列

#### Reduction
在這個問題中，我們試圖把問題化約成最大互斥邊路徑問題 :
1. 先用 DP 求出「以第 $i$ 項為結尾時的 LIS 的長度」，並找出最長 LIS 為 $n$
2. 建立一個虛擬的源點 $s$ 與虛擬的匯點 $t$
3. 將每個元素 $i$ 拆分成兩個節點 $i$ 與 $i'$，並連邊 $i\to i'$
4. 若 $dp[i]=1$，則 $s\to i$；若 $dp[i]=n$，則 $i'\to t$

<center>
<img src="https://hackmd.io/_uploads/Hyz0Jnzqxx.png" style="margin: 0 auto; display: block; width: 500px">
</center>

如此一來，每個 LIS 都會代表一條 $s\to t$ 的路徑。因此，**同時取最長遞增子序列問題**就可以 reduce 成**最大互斥邊路徑問題**。如果要進一步化成流量網路的話，只要把容量都設為 $1$ 即可

<center>
<img src="https://hackmd.io/_uploads/B18Henfqeg.png" style="margin: 0 auto; display: block; width: 500px">
</center>

## 最小花費最大流量問題 Min-cost Max-flow Problem
這個東西太長了，所以我們簡稱 MCMF 問題。也有人會簡稱 min-cost flow

### 問題簡述
給一張帶權重的流量網路 $N_w$，每一個單位流量經過邊 $e$ 時都需加上邊權 $w(e)$，請問若送出的流量為 $d$，則送達 $t$ 最小權重和為多少呢?

註 : 大多數時候會把邊的權重稱為「花費 (cost)」

### 解法 : SPFA-flow 演算法
這在這篇有講過了，這裡就不多提，總之就是一個 MCMF 的 solver

### 小技巧 : 線性規劃
MCMF 的線性規劃可以寫成 :

$$
\begin{aligned}
\min\quad & \sum_{(u, v)\in E} w(u, v)\cdot f_{uv}\\
\text{s.t.}\quad
&f_{uv}\leq c(u, v)\quad\forall u, v\in V\\
&\sum_{v\in V} f_{vu}-\sum_{v\in V} f_{uv}=0\quad\forall u\in V-\{s, t\}\quad\\
&\sum_{v\in V} f_{sv}-\sum_{v\in V} f_{vs}=d\\
&f_{uv}\geq0\quad\forall u, v\in V
\end{aligned}
$$

有時候如果不知道題目怎麼解的話，可以把要最佳化的目標函數跟限制寫下來 (幫助大腦整理資訊)。如果長得像 MCMF 的線性規劃式子，那可以試試看 MCMF

### 最大流量問題化約成 MCMF 問題
把最大流量問題 instance 中的每條邊加上權重為 $0$ 就完成了

### 最大花費流問題 Max-cost Flow Problem
#### 問題簡述
給一張帶權重的流量網路 $N_w$，每一個單位流量經過邊 $e$ 時都需加上邊權 $w(e)$，請問若送出的流量為 $d$，則送達 $t$ 「最大」權重和為多少呢?

#### Reduction
這很簡單，原因也很 trivial，只給方法不解釋 :
1. 把每條邊的花費加個負號
2. 跑 MCMF solver
3. 將答案取負號

### 翻轉限制技巧 Flipping Constraints Technique

有時候我們會遇到一個問題 : 「同一條路可以走兩次，第一次可以拿到 $c$ 元，第二次沒錢拿，請問從起點走到終點最多可以達到多少錢?」像是這樣的問題，我們一樣可以用 MCMF 來解。以下圖為例 :

<center>
<img src="https://hackmd.io/_uploads/B1EXxazqlg.png" style="margin: 0 auto; display: block; width: 700px">
</center>

我們可以將邊拆成兩個 :
- 一條邊容量為 $1$、花費為 $-c$
- 一條邊容量為 $\infty$、花費為 $0$

這其實是透過最大流的「瓶頸」來達成的技巧，因為容量為 $1$ 的邊如果是 augmenting path 的一部分，那它下次就不可能再當一次 augmenting path (flow 是滿的)。之後走的邊肯定是容量無限的那條，而花費當然也只會是 $0$。這樣就可以跑 max-cost flow 囉

[深海機器人問題](https://www.luogu.com.cn/problem/P4012)是這個技巧的裸題，可以寫寫看

## 二分圖最大權匹配問題 Maximum Weighted Matching Problem
注意 : 以下都是二分圖的問題，如果是一般圖不見得可以這樣解 (有些甚至沒辦法解)

### 問題簡述
如果我們把二分圖每條邊都給一個權重 $w:V\times V\rightarrow \mathbb{R^+}$。那麼最大權匹配總和是多少呢?

### 解法 : [匈牙利演算法 (KM 演算法)](https://hackmd.io/@ShanC/Hungarian-Algorithm)
在之前的章節有講過了，匈牙利演算法可以直接把二分圖最大權完美匹配問題解掉。如果是 $K_{n, m}$，$n \neq m$，那就加上「虛擬點」與「虛擬邊」，並將權重設為 $0$。因此這是將**二分圖最大權匹配問題**的 instance 化約成**二分圖最大權完美匹配問題**的 instance

<center>
<img src="https://hackmd.io/_uploads/rkBRVRAKxl.png" style="margin: 0 auto; display: block; width: 700px">
</center>

### 解法 : 化約成 MCMF 問題 Reduce to MCMF Problem
給定二分圖 $G=(U,V,E)$ 與邊權 $w(u,v)$

#### 建圖
- 建立源點 $s$ 與匯點 $t$
- 對每個 $u\in U$ : 加邊 $s \to u$，容量 $1$，費用 $0$
- 對每個 $v\in V$ : 加邊 $v \to t$，容量 $1$，費用 $0$
- 對每條 $(u,v)\in E$ : 加邊 $u \to v$，容量 $1$，費用 $-w(u,v)$
(因為我們要在最小費用下，等價於最大化總權重)

#### 取解
- 路徑上用到的 $u\to v$ 邊 (流量為 1) 就是被選到的匹配邊
- 總費用最小 ⇔ 總權重最大 (因為費用設成 $-w$ 或 $C-w$)
- 容量都設為 1，保證每個 $u$ 與 $v$ 最多被配一次 (約束匹配)
- 送出一單位 $s\to u\to v\to t$ 的流，就等於選了邊 $(u,v)$
- 把邊費用設為 $-w$ (或 $C-w$)，最小化總費用就會偏好高權重的邊，於是得到最大權

<center>
<img src="https://hackmd.io/_uploads/Sk_Ekgy5ee.png" style="margin: 0 auto; display: block; width: 700px">
</center>

因此這算是**二分圖最大權匹配問題**的 instance 化約成 **MCMF 問題**的 instance

## 二分圖最大匹配問題 Bipartite Matching Problem

### 問題簡述
給一張二分圖，請問最大 (基數) 匹配為何?

### 解法 : [擴充路徑演算法](https://hackmd.io/@ShanC/Augmenting-Path-Algorithm)
根據 [Berge 定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem#Berge-%E5%AE%9A%E7%90%86)，「一個匹配 $M$ 是圖 $G$ 的最大匹配若且唯若 $G$ 沒有 $M$ 的擴充路徑」，**擴充路徑演算法**就是利用這個原理來跑。值得注意的是，這裡的擴充路徑 (增廣路徑) 與 flow 演算法所描述的是不同的東西，他們撞名了

<center>
<img src="https://hackmd.io/_uploads/Syzc7doP1l.png" style="margin: 0 auto; display: block; width: 500px">
</center>
<p class="text-center">
圖源 : D.B.West - Introduction to Graph Theory 2/e p.113
</p>

### 解法 : [匈牙利演算法 (KM 演算法)](https://hackmd.io/@ShanC/Hungarian-Algorithm)
之前的章節有講過了，匈牙利演算法是用於求解最大權匹配問題，但是當我們把權重改成 $1$ 之後，就可以直接求解最大 (基數) 匹配了。因此我們這裡可以把它看作是**二分圖最大匹配問題**的 instance 化約成**二分圖最大權匹配問題**的 instance

### 解法 : 化約成最大流問題 Reduce to Max-flow Problem
我在[這篇](https://hackmd.io/@ShanC/bipartite-and-flow#%E6%9C%80%E5%A4%A7%E6%B5%81-%E6%9C%80%E5%B0%8F%E5%89%B2%E5%AE%9A%E7%90%86%E8%88%87-K%C5%91nig-Egerv%C3%A1ry-%E5%AE%9A%E7%90%86)講過並證明了[最大流-最小割定理](https://hackmd.io/@ShanC/maxflow-mincut-theorem)效力等價於 [Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)。事實上，**二分圖最大匹配問題**的 instance 化約成**最大流問題**的 instance 也是一模一樣。因此細節就不再多提了

<center>
<img src="https://hackmd.io/_uploads/Bk2R6AWelx.png" style="margin: 0 auto; display: block; width: 700px">
</center>

如此化約之後，就可以得到結論 :
$$
G\mathrm{的最大匹配}=N\mathrm{的最大流量}
$$

### 二分圖最小點覆蓋問題 Minimum Vertex Cover Problem
#### 問題簡述
一張二分圖 $G$ 最少需要幾個節點才能覆蓋所有邊呢?

#### Reduction
根據 [Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem) : $\alpha'(G)=\beta(G)$
因此找出二分圖最大匹配就可以找出二分圖最小點覆蓋
<center>
<img src="https://hackmd.io/_uploads/BJ8OVEsPJe.png" style="margin: 0 auto; display: block; width: 250px">
</center>

### 二分圖最小權點覆蓋問題 Minimum Weighted Covering Problem
#### 問題簡述
一張帶點權的二分圖 $G$ 最少挑哪些點才能覆蓋所有邊並且權重總和最小?

#### Reduction
雖然有 [Egerváry 定理](https://hackmd.io/@ShanC/Hungarian-Algorithm#Egerv%C3%A1ry-%E5%AE%9A%E7%90%86)「$\mathrm{二分圖最大權匹配}=\mathrm{二分圖最小權}$」，但是這個定理講的比較像是一個「浮動」的點權，因此匈牙利算法解不出來。正確做法是 reduce 成**最小割問題**

1. 給定二分圖 $G=(U,V,E)$，點權 $w(x)\ge 0$
- 新增源點 $s$、匯點 $t$（有向網路）
- 對每個 $u\in U$：加邊 $s\to u$，容量為 $w(u)$
- 對每個 $v\in V$：加邊 $v\to t$，容量為 $w(v)$
- 對每條 $(u,v)\in E$：加邊 $u\to v$，容量為 $\infty$
2. 求一個最小 $s$–$t\text{ cut}$，得到分割 $[S,T]$（$s\in S, t\in T$）
3. 把點覆蓋取為 $C \;=\; (U\cap T)\;\cup\; (V\cap S)$ 就是答案

<center>
<img src="https://hackmd.io/_uploads/SJ6BxJflxe.png" style="margin: 0 auto; display: block; width: 520px">
</center>

如此一來就成功把**二分圖最小權點覆蓋問題**化約成**最小割問題**。當然我們也可以把**二分圖最小點覆蓋問題** reduce 成這個問題

### 二分圖最小邊覆蓋問題 Minimum Edge Cover Problem
#### 問題簡述
一張二分圖 $G$，最少需要幾條邊才能覆蓋所有節點呢?

#### Reduction
根據[定理 [Gallai 1959]](https://hackmd.io/@ShanC/konig-theorem#%E5%AE%9A%E7%90%86-1-Gallai-1959) 可得「所有點的數量 $-$ 最大匹配數$=$最小邊覆蓋」

### 二分圖最大獨立集問題 Maximum Independent Set Problem
#### 問題簡述
一張二分圖 $G$ 的最大獨立集有多大呢?

#### Reduction
根據[引理](https://hackmd.io/@ShanC/konig-theorem#%E5%BC%95%E7%90%86-1)可得「所有點的數量減去最小點覆蓋數$=$最大獨立集大小」

### 二分圖最小花費 (基數) 匹配問題 Min-cost Bipartite Matching Problem
#### 問題簡述
在一個帶花費的二分圖，每次把一條邊 $e$ 加進匹配中就需要加上該邊花費 $c(e)$，請問最大匹配的最小花費為何?

#### Reduction
要注意這**不是**最大權匹配，兩者區別很大別搞混。考慮以下建圖方式 :
1. 在二分圖的每一條邊 $e$ 容量為 $\infty$、花費為 $c(e)$
2. 將左邊的獨立集的所有節點 $u$ 建一條邊 $s\to u$
3. 將右邊的獨立集的所有節點 $v$ 建一條邊 $v\to t$

如此一來就將**二分圖最小花費 (基數) 匹配問題** reduce 成 MCMF 問題

### 二分圖容量匹配問題 B-matching Problem
#### 問題簡述
給一張二分圖 $G=(U, V, E)$，允許每個節點 $v$ 可以最多匹配 $b(v)$ 條邊，求最大匹配

<center>
<img src="https://hackmd.io/_uploads/SJVkhm1qlx.png" style="margin: 0 auto; display: block; width: 520px">
</center>

上圖的實線就是一組合法解

#### Reduction
我們把問題轉換成最小割 :
1. 在二分圖中，從源點 $s$ 連到 $u\in U$，權重設為 $b(u)$
2. 從 $v\in V$ 連到匯點 $t$，權重設為 $b(v)$
3. $u\to v$ 的邊權重設為 $1$
4. 最小割結果對應到最大 b-matching

出現在 $[U, V]$ 的最小割就是匹配邊

<center>
<img src="https://hackmd.io/_uploads/S1I_0mJ9lx.png" style="margin: 0 auto; display: block; width: 520px">
</center>

如此一來，就可以把 **b-matching 問題**化約為**最小割問題**

## 網格化約技巧 Reduction on Grid
網格是我們在玩圖論問題時很常遇到的題型，通常這種題目都有特定的建圖技巧

### 奇偶建圖
把每個格子編號 (如下圖)，相鄰的格子肯定是奇偶相鄰。我們將這種建圖方式稱為奇偶建圖

<center>
<img src="https://hackmd.io/_uploads/B1XnHRatex.png" style="margin: 0 auto; display: block; width: 400px">
</center>

#### 引入問題 : [方格取數問題](https://www.luogu.com.cn/problem/P2774)
有一個 $m$ 行 $n$ 列的網格圖，每個方格中都有一個正整數。現要從方格中取數，使任兩個數所在方格沒有公共邊，且取出的數的總和最大，請求出最大的和

#### 輸入

3 3
1 2 3
3 2 3
2 3 1 

#### 輸出

11

#### 題解
藉由上面的範測，我們來觀察一下
1. 當我們把這張圖相鄰的格子連起來，顯然這張圖是一張二分圖，因為奇數點無法與奇數點相鄰、偶數點無法與偶數點相鄰

<center>
<img src="https://hackmd.io/_uploads/BJIRjAptlx.png" style="margin: 0 auto; display: block; width: 400px">
</center>

2. 說到二分圖，我們最先想到的就是最小割。在這一題，我們需要「取節點」，而不是「取邊」。所以顯然在弄成 flow 圖之後，我們想割的邊就是直接連至 $s$ / $t$ 的邊。因此其餘的邊我們一律寫上容量為 $\infty$

<center>
<img src="https://hackmd.io/_uploads/H13lR0TFll.png" style="margin: 0 auto; display: block; width: 400px">
</center>

3. 現在只剩容量還沒處理好，基本上就是把原本的點權放上去就好。注意到我們在這張圖所求的是「最小割」，如果要求出最大，那就需要用總和去扣掉最小

<center>
<img src="https://hackmd.io/_uploads/rkwJeyAFgg.png" style="margin: 0 auto; display: block; width: 400px">
</center>

最後來畫畫 $s$-$t\text{ cut}$，驗證一下正不正確

<center>
<img src="https://hackmd.io/_uploads/HJDE-JAKxe.png" style="margin: 0 auto; display: block; width: 400px">
</center>

算一下，$\mathrm{cut}(s, t)=1+3+2+2+1=9$，$\mathrm{總和}-\mathrm{cut}(s, t)=20-9=11$
正確答案

所以這其實是使用**二分圖最小權點覆蓋**來解**方格取數問題**

#### 備註
其實這題也可以說是**二分圖帶權最大獨立集問題**，只是剛好定理 $n(G)-\beta(G)=\alpha(G)$ 放在帶權圖也適用，因此也可以看成是**二分圖最小權點覆蓋**

#### 實作程式碼
- `grid[i][j]` : 第 $i$ 列第 $j$ 行的正整數
- `idx[i][j]` : 第 $i$ 列第 $j$ 行的節點編號
- `total` : 所有數字的總和
- `dir` : 方位

/* 略 */
s = 0, t = n * m + 2, cnt = 0;
flow.init(n * m + 3, s, t);

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        num[i][j] = ++cnt;
        total += grid[i][j];
        
        if ((i + j) % 2)  // odd
            flow.add_edge(num[i][j], t, grid[i][j]);
        else              // even
            flow.add_edge(s, num[i][j], grid[i][j]);
    }
}
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < 4 && (i + j) % 2 == 0; k++) {
            // 相鄰的建邊，偶連到奇
            int dx = i + dir[k][0], dy = j + dir[k][1];
            flow.add_edge(num[i][j], num[dx][dy], INF);
        }
    }
}
cout << total - flow.flow() << '\n';
/* 略 */

### 行列建圖
有時後我們會希望可以表達「網格上一個方格 $(i, j)$ 可以跳到同一行 $i$ 的任一格或同一列 $j$ 的任一格」可以利用這個技巧

#### 引入問題 : [青蛙跳格子問題](https://atcoder.jp/contests/arc074/tasks/arc074_d?lang=en)
有一隻青蛙在 $n\times m$ 網格中的格子 $S$，青蛙每次移動都可以跳到同一行或同一列的荷葉上，最後可以跳到格子 $T$。請問最少需要拿掉幾片荷葉才能使青蛙無法跳到 $T$ ?

#### 輸入
`'o'` 代表荷葉、`'.'` 代表沒東西

3 3
S.o
.o.
o.T

#### 輸出

2

#### 題解

一樣我們先觀察圖，試著用最直觀的方式畫畫看

<center>
<img src="https://hackmd.io/_uploads/SJtZ2_AKxe.png" style="margin: 0 auto; display: block; width: 500px">
</center>

感覺好像可以直接建圖，我們再多加一片荷葉看看

<center>
<img src="https://hackmd.io/_uploads/SkMta_0Fll.png" style="margin: 0 auto; display: block; width: 500px">
</center>

不難注意到 :
1. 這張圖是無向圖 (兩方向皆可)，可能會有很多環
2. 每一行要花 $O(n^2)$ 的時間建圖；每一列要花 $O(m^2)$ 的時間建圖
3. $S$ 會有入點、$T$ 會有出點

如果你熟悉 Dinic 會知道，這種方式跑一定會爆，所以顯然這不是個好方法

注意到每個在第 $i$ 行的節點都可以互相往來；每個第 $j$ 列的節點都可以互相往來。利用這一性質，我們可以造一些行與列「虛擬點」。考慮以下步驟 :

1. 我們先將虛擬點編號

<center>
<img src="https://hackmd.io/_uploads/r1yrbYAFxx.png" style="margin: 0 auto; display: block; width: 500px">
</center>

2. 把虛擬點在出來後，若存在一片荷葉在 $(i, j)$，就將第 $i$ 行的虛擬點與第 $j$ 列的虛擬點相連 (這邊先看成是無向圖)。

<center>
<img src="https://hackmd.io/_uploads/SkCibOVqee.png" style="margin: 0 auto; display: block; width: 500px">
</center>

3. 我們把源點 $S$ 跟匯點 $T$ 都加上去。注意前面連的都是無向邊 (雙向都要連)，$S$ / $T$ 連的是有向邊

<center>
<img src="https://hackmd.io/_uploads/rk1Mz_4cxl.png" style="margin: 0 auto; display: block; width: 500px">
</center>

4. 每片荷葉都代表一條邊，所以我們要求的其實是此圖的最小邊割，容量設為 $1$。由於不希望割到荷葉以外的邊，與 $S$ / $T$ 相連的邊容量都設為 $\infty$

<center>
<img src="https://hackmd.io/_uploads/SkNVMdVqgg.png" style="margin: 0 auto; display: block; width: 500px">
</center>

如此一來我們就可以用**最小割問題**的 solver 來解掉**青蛙跳格子問題**

#### 實作程式碼

/* 略 */
int s = 0, t = n + m + 2;
flow.init(n + m + 5, s, t);
for (int i = 1; i <= n; i++) {             // 1-based
    for (int j = n + 1; j <= m + n; j++) { // 注意 : 編號不可與 i 重複
        char c;
        cin >> c;
        if (c == 'S') {
            flow.add_edge(s, i, INF);
            flow.add_edge(s, j, INF);
        }
        else if (c == 'T') {
            flow.add_edge(i, t, INF);
            flow.add_edge(j, t, INF);
        }
        else if (c == 'o') {
            flow.add_edge(i, j, 1);
            flow.add_edge(j, i, 1);
        }
    }
}

int ans = flow.flow();
cout << (ans >= INF ? -1 : ans) << '\n';
/* 略 */

像是在前幾篇的[這題](https://hackmd.io/@ShanC/Augmenting-Path-Algorithm#%E4%BE%8B%E9%A1%8C%E8%AA%AA%E6%98%8E)寫然也是這種建圖方法

## 最小路徑覆蓋問題 Minimum Paths Cover Problem
### 問題簡述

給定一張有向無環圖 $G$，請問最少需要幾條路徑，才可以使得每個點都剛好在一條路徑上?

<center>
<img src="https://hackmd.io/_uploads/S1zQdEy5gx.png" style="margin: 0 auto; display: block; width: 500px">
</center>

如上圖，答案是 $2$ 條路徑

### 解法 : 化約成二分圖最大匹配問題 Reduce to Bipartite Maximum Matching Problem
因為其他網路上的資料太過通靈，因此我這邊提出比較合理的看法
給一張節點數為 $n$ 的有向無環圖 $D$
1. 由於這是有向無環圖 $D$，所形成的路徑肯定每個節點都只有一條出邊，僅最後一點沒有，因此得到
$$
\mathrm{覆蓋路徑數量}=\mathrm{沒有出邊的節點數}
$$

<center>
<img src="https://hackmd.io/_uploads/Sy_0-Hyqxe.png" style="margin: 0 auto; display: block; width: 500px">
</center>

2. 從有向圖的邊定義來看，每條邊 $(v, v')$ 都是 $V\times V$ 裡的元素。若我們把兩個 $V$，當作是不同的集合 $V$ 與 $V'$，因為同一個集合裡的元素不會連邊，兩集合分別都是獨立集。這個 $D$ 中由邊的定義所形成 $V$ 與 $V'$ 很自然地會形成二分圖
注意 : 因為這是有向圖，$v\to u$ 不代表 $u\to v$，因此在二分圖中只會連 $(v, u)$ 而不會連 $(u, v)$

<center>
<img src="https://hackmd.io/_uploads/By5VMr19gx.png" style="margin: 0 auto; display: block; width: 500px">
</center>

3. 顯然 $D$ 中每條覆蓋路徑上的邊都會對應到二分圖的一條邊。因此 :
$$
\mathrm{最少路徑覆蓋的「邊數」}=\mathrm{二分圖最大匹配}
$$
從 1. 得到 :
$$
\mathrm{覆蓋路徑數量}=\mathrm{沒有出邊的節點數}
$$
又因為發現路徑覆蓋中沒有出邊的端點，當然也不會匹配到任何東西，所以 :
$$
\mathrm{「最少」沒有出邊的節點數}=n-\mathrm{二分圖最大匹配}
$$
故
$$
\mathrm{「最少」覆蓋路徑數量}=n-\mathrm{二分圖最大匹配}
$$

如此一來**最小路徑覆蓋問題**就可以被 reduce 成**二分圖最大匹配問題**

## 專案選擇問題 Project Selection Problem
這問題有名到連維基百科都查得到，有時會看到簡稱 PSP 來表示此問題

### 問題簡述
給你 $N$ 個專案 $E=\{E_1,\cdots, E_N\}$ 與 $M$ 台機器 $I=\{I_1,\cdots,I_M\}$，如果你執行了專案 $E_i$ 就可以拿到 $p_i$ 元，如果你買了機器 $I_j$ 就需花費 $q_j$ 元。已知專案 $i$ 需要用到的機器為 $R_i\subseteq I$，且兩個專案可以用同一台機器 (不用重複購買)，你可以選擇執行哪些專案。請問怎麼選擇才會使收益最大?

註 : 其實就是求在符合上述規則的情況下
$$
\max\sum p_i-\sum q_j
$$

### 解法 : 化約成最小割問題 Reduce to Min-cut Problem
我們先建圖再來觀察

#### 建圖
1. 所有 $E_i$ 連邊 $s\to E_i$，容量為 $p_i$
2. 所有 $I_j$ 連邊 $I_j\to t$，容量為 $q_j$
3. 所有 $R_i$ 中，所有 $r\in R_i$ 連邊 $E_i\to r$，容量為 $\infty$

#### 觀察
以下圖為例，這是一個有兩個專案與四台機器的例子，機器沒有重複使用，建好圖會長這樣 :
<center>
<img src="https://hackmd.io/_uploads/SJAnmCz9eg.png" style="margin: 0 auto; display: block; width: 500px">
</center>

顯然可以看到
- 若執行 $E_1$，則會虧損 $20$ 元
- 若執行 $E_2$，則會賺 $52$ 元

觀察最小割的位置，都會割在「瓶頸」的邊上，也就是錢比較少的地方

<center>
<img src="https://hackmd.io/_uploads/SyF2BRG9ge.png" style="margin: 0 auto; display: block; width: 500px">
</center>

根據上述觀察，不難發現 :
- 若割在 $s\to E_i$ 的地方，則收入 $<$ 支出
- 若割在 $I_j\to t$ 的地方，則收入 $>$ 支出

結論 : 若我們只挑「收入 $>$ 支出」的專案，則會有最大收益

#### 求解
先設一些變數，等等方便推導 :
- $a$ : 會賺錢的專案所拿到的收入
- $b$ : 不會賺錢的專案所拿到的收入
- $c$ : 會賺錢的專案會使用的機器支出
- $d$ : 不會賺錢的專案會使用的機器支出
- $m$ : min-cut 的邊權總和，就是 $b+c$
- $a+b=\sum p_i$

我們要求的「最大收益」為 $a-c$
$$
\begin{aligned}
a-c&=a+(b-b)-c\\
&=(a+b)-(b+c)\\
&=a+b-m\\
&=\sum p_i-m
\end{aligned}
$$

所以 $\sum p_i-m$ 就是所求的最大收益

[這題](https://www.luogu.com.cn/problem/P2762)算是裸題可以寫寫看

#### 舉例說明
上面的例子是沒有用到同一個機器，來舉個需要用到同一台機器的例子 :
- 專案 : $E=\{E_1, E_2\},\quad p_1=10,\quad p_2=25$
- 機器 : $I=\{I_1, I_2, I_3\},\quad q_1=5,\quad q_2=6,\quad q_3=7$
- $R_1=\{I_1, I_2\},\quad R_2=\{I_2, I_3\}$

可以這樣建圖 :

<center>
<img src="https://hackmd.io/_uploads/H1b3vhXqxl.png" style="margin: 0 auto; display: block; width: 500px">
</center>

不難發現最小割的位置都是在機器的地方。若想求解，我們可以算 :
- $\sum p_i=10+25=35$
- $m=5+6+7=18$
- $\text{最大收益}=\sum p_i-m=35-18=17$

### 拓展問題 : $B$ 專案執行完才能執行 $A$ 專案
#### 問題簡述
同樣是專案選擇問題，但我們來多加一些限制 : 「$B$ 專案執行完才能執行 $A$ 專案，且 $A$ 專案不需要任何機器」

#### Reduction
我們可以考慮加一條容量為 $\infty$ 的邊 $A\to B$，其餘都與前一問題相同，如此一來 :
- 邊 $A\to B$ 絕對不會是最小割
- 如果一個單位 flow 要流過 $A$，那一定也要流過 $B$ 才能到達匯點 $s$

#### 拓展
同樣的事也可以發生在機器。其實不難看出這樣的拓展已經跟誰是專案、誰是機器沒什麼關係了，因為這個問題當中，我們只在乎「節點 $B$ 要『依靠』節點 $A$ 才能有流量 flow 過去」因此建容量 $\infty$ 的邊 $A\to B$

### 最大權閉合子圖問題 Maximum Closure Problem

#### 閉合子圖
給一個有向無環圖 $D$，閉合子圖 $C$ 是指其中的子圖，使得不存在邊從 $C$ 指向 $D\setminus C$。換句話說就是，存在一條邊 $u\to v$，若 $u\in C$ 則 $v\in C$

#### 問題簡述
給一個帶點權的有向無環圖 $D$，請問最大權的閉合子圖權重和為多少呢?

#### Reduction
將 $D$ 的所有邊加上 $\infty$ 的容量。若點權為正，則從 $s$ 連到該點；若點權為負，則從該點連到 $t$

<center>
<img src="https://hackmd.io/_uploads/SyqBlamclg.png" style="margin: 0 auto; display: block; width: 500px">
</center>

可以把點權 $>0$ 的邊當作是收入、點權 $<0$ 的邊當作是支出，剩下的邊只是他們的「依靠」關係。這樣就 reduce 完了

### 備註 : 如何分辨專案選擇問題?
如果遇到以下幾點，可以試著把題目轉乘專案選擇問題 / 最大權閉合子圖問題 :
- 有明確的「收入」與「支出」
- 最大化收益
- $A$ 必須在 $B$ 完成之後才能做

## 題目練習
[CSES Download Speed](https://cses.fi/problemset/task/1694) (flow 裸題)
[CSES Police Chase](https://cses.fi/problemset/task/1695/) (割裸題)
[CSES Task Assignment](https://cses.fi/problemset/task/2129) (完美匹配裸題)
[CSES School Dance](https://cses.fi/problemset/task/1696) (匹配裸題)
[Codeforces 653D. Delivery Bears](https://codeforces.com/problemset/problem/653/D)
[CSES Grid Puzzle I](https://cses.fi/problemset/task/2432) (b-matching 裸題)
[CSES Grid Puzzle II](https://cses.fi/problemset/task/2131) (帶權 b-matching 裸題)
[CSES Distinct Routes](https://cses.fi/problemset/task/1711/) (Menger 定理裸題)
[CSES Distinct Routes II](https://cses.fi/problemset/task/2130/) (帶權 Menger 定理裸題)
[CSES Parcel Delivery](https://cses.fi/problemset/task/2121) (MCMF 裸題)
[AtCoder Regular Contest 074F - Lotus Leaves](https://atcoder.jp/contests/arc074/tasks/arc074_d?lang=en) (行列建圖裸題)
[AtCoder Beginner Contest 259G - Grid Card Game](https://atcoder.jp/contests/abc259/tasks/abc259_g) (把不要的割掉)
[AtCoder Beginner Contest 224H - Security Camera 2](https://atcoder.jp/contests/abc224/tasks/abc224_h) (二分圖最大費用匹配)
[AtCoder Beginner Contest 274G - Security Camera 3](https://atcoder.jp/contests/abc274/tasks/abc274_g) (最小點覆蓋)
[AtCoder Regular Contest 085E - MUL](https://atcoder.jp/contests/arc085/tasks/arc085_c) (半裸的拓展專案選擇)
[Codeforces 498C. Array and Operations](https://codeforces.com/problemset/problem/498/C)
[2017ICPC World Finals - C Mission Improbable](https://codeforces.com/gym/101471/attachments) (假設格子都拿完，目標就變成放回，要怎麼放呢?)
[Codeforces 1082G. Petya and Graph](https://codeforces.com/problemset/problem/1082/G) (誰是收入誰是支出? 看清楚就是裸題)
[2015ICPC 西安 - C The Problem Needs 3D Arrays](https://codeforces.com/gym/100548/attachments) (最大稠密子圖，這篇沒講到)
[BAPC14 - A Avoiding the Apocalypse](https://codeforces.com/gym/101512/attachments) (對時間做拆點分層)
[2018 ACM-ICPC, Universidad Nacional de Colombia - F. UN Finals](https://codeforces.com/gym/101845/problem/F)
[AtCoder Beginner Contest 225G - X](https://atcoder.jp/contests/abc225/tasks/abc225_g) (||專案選擇/閉合子圖||)
[AtCoder Beginner Contest 193F - Zebraness](https://atcoder.jp/contests/abc193/tasks/abc193_f) (最小割=選擇的那對，要做一些轉換)
[AtCoder Regular Contest 142E - Pairing Wizards](https://atcoder.jp/contests/arc142/tasks/arc142_e) (這題的建點很妙)
[AtCoder Beginner Contest 247G - Dream Team](https://atcoder.jp/contests/abc247/tasks/abc247_g) (這題要想想你的模板在做什麼)
[AtCoder Beginner Contest 421G - Increase to make it Increasing](https://atcoder.jp/contests/abc421/tasks/abc421_g)

----

## 參考資料
- D.B.West - Introduction to Graph Theory 2/e
- CLRS - Introduction to Algorithms, Fourth Edition
- [[Tutorial] Maximum Flow and Minimum Cost Maximum Flow (to prove greedy)](https://codeforces.com/blog/entry/110328)
- [Solving Problems with Min Cut Max Flow Duality](https://codeforces.com/blog/entry/136761)
- [台師大演算法筆記 - matching](https://web.ntnu.edu.tw/~algo/Matching2.html)
- [海大競程 - Classic Flow Problems](https://hackmd.io/@LeeShoWhaodian/ClassicFlowProblems#/)
- [海大競程 - 匹配與網路流](https://hackmd.io/@LeeShoWhaodian/2024flow#/)
- [[Tutorial, Flows] Project Selection Problem](https://codeforces.com/blog/entry/101354)
- [Project Selection Problem for k-ary variables (Burn and Bury Problem)](https://shenpengfii.github.io/programming/algorithm/k-ary%20PSP)
- [Wikipedia - Maximum flow problem](https://en.wikipedia.org/wiki/Maximum_flow_problem)
- [Wikipedia - Minimum-cost flow problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem#Minimum_weight_bipartite_matching)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/9/2