# flow network

## 一些名詞定義

==$cut(S,T)$==

把 flow network 裡面的 vertices 分成兩部分，一部分是 $S$，另一部分是 $T = V-S$

==$net \ flow \quad f(S,T)$==

「$S$ 裡的點」到 「$T$ 裡的點」邊上的 flow
扣掉反方向 「$T$ 裡的點」到 「$S$ 裡的點」邊上的 flow

> 可直接看下圖例子比較清楚


==$capacity \ of \ cut \quad c(S,T)$==

「$S$ 裡的點」到 「$T$ 裡的點」的邊的 capacity
> 可直接看上方圖

## Algo
### Ford Fulkerson

#### code

code 的意義：
> 不斷從 residual network 找 augmenting path 加入，直到沒有 augmenting path

#### 條件 ／ 特點

- 根據 <font color = "green">max-flow-min-cut</font> Thm， ++residual network 裡沒有 augmenting path++ 等價於 ++flow 已達到 max++

- 雖然 max-flow problem 大部分的 capacity 都是整數，但是<font color = "red">++有理數++也可以</font>！
> 我們可以透過適當的 scaling transformation 把所有邊的 capacity 都調成整數

#### Time

假設經過 scaling transformation 後，++transformed network 裡的 max flow++ 是 <font color = "snake">$f^*$</font> ，則 Ford Fulkerson 的 time：

<font color = "red">$O(|E|f^*)$</font>

##### 分析

因為 Ford Fulkerson 的概念是不斷找 augmenting path 直到找不到為止，所以我們每一輪就是找一條 augmenting path，我們將$O(|E|f^*)$ 分成兩部分解釋，一是 $|E|$ 從哪來，二是 $f^*$ 從哪來：

1. $O(|E|f^*)$ 裡的<font color = "green"> $|E|$</font> 代表找的時間，不管是用 DFS 找或 BFS 找，時間都是 $O(V+E')$ ，也就是 $O(E)$

> $E'$ 就是在畫 residual network 的那些邊
> 包含：
> a. 原圖中 capacity 不是 0 的邊
>> （因為 residual network 中 capacity = 0 的邊可省略不畫）
>>
> b. 倒退邊

- 雖然不管是 DFS 或 BFS 都可以，但一般來說講 Ford Fulkerson 通常會假設是用 DFS ，如果強制要求用 BFS 是指 Edmonds Karp（可參考下節內容）

2. $O(|E|f^*)$ 裡的<font color = "green"> $f^*$ </font>代表最多跑幾輪（增加幾條 augmenting path）

>$f^*$ 是指 flow 的最大值，會加一個 $*$ 是因為前面有講到，在一個 flow network 中，邊的那些 capacity 是可以不是整數，只要是有理數就行的，因為我們可以透過適當的轉換把這些有理數轉成整數，那 $f^*$ 就是轉換後最大的 flow

那為什麼最多是做 $f^*$ 輪呢？

因為既然要新增 augmenting path ，代表 flow 好歹要加 1（否則加 0 等同沒做事，就不用新增啦），所以每一輪至少加 1 的情況下，最多輪的情形就是每一輪都只加最少的量，也就是每輪都只加 1，這樣等同要做 $f^*$ 輪

---

### Edmonds Karp

#### code


和 Ford Fulkerson 基本上相同，除了在第三行找 augmenting path 時把每個邊的 distance / weight 設成 1，再用 <font color = "green">BFS</font> 找 shortest path

關於為什麼要找最短的 path，可參考[這篇文章](https://www.desgard.com/algo/docs/part4/ch03/4-edmond-karp/)
> 是別人的文章，我覺得寫得很清楚，如果有不妥請告知我，謝謝～

#### 條件 ／ 特點

- augmenting path 的長度是 monotonically increasing

> monotonically increasing 定義:
>
> $f(n) \ is \ monotonically \ increasing$
> $if \ m \le n, \quad then \ f(m) \le \ f(n)$
>> 也就是 non-decreasing （只要沒有 decrease 即可）

#### Time

Edmonds Karp time = <font color = "red">$O(VE^2)$</font>

> 105 交 52.
> 給 Edmonds Karp time = $O(V^2E)$ 正確，不知道後來有沒有修正，還是 $O(V^2E)$ 也對？

##### 分析

因為使用 DFS 找 augmenting path，每找一條 path 需要花 DFS 的時間 = $O(E)$
> 詳細可參考上方 Ford Fulkerson

根據定理，<font color = "red">最多增加 $O(VE)$ 條 augmenting path</font>，等同最多做 $O(VE)$ 輪
> 證明在 *CLRS p.729 Thm 26.8*

做 $O(VE)$ 輪，每輪花的時間是 $O(E)$，所以時間即兩者相乘 = $O(VE^2)$

## 題目不符合 flow network 的處理

#### 處理 antiparallel 的問題

flow network 要求如果某兩點 u, v 間有一個 u 到 v 的邊
> i.e. $(u,v) \in E$

則 v 到 u 不能有邊
> i.e. $(v,u) \notin E$

我們把$(u,v)$ 和 $(v,u)$ 稱作 <font color = "snake">antiparallel</font>

如果題目給的圖有 antiparallel edges，解決方法就是在這兩個點中插入一個中介點，其中一個原本的 edge 不變，另一個改為經過這個中介點

例子：

> 插入中介點 $v'$

#### 處理 multisource / multisink

如果有多個 source，則加入一個 <font color = "snake">supersource</font> ，連到所有這些 souces

同理如果有多個 sink，則加入一個<font color = "snake">supersink</font>，把所有的 sinks 連到這個 supersink

- 且 capacity 都設 $\infty$

例子：