大綱

• 流的定義
• 最大流演算法
  • FF
  • EK
  • Dinic
• 最大流問題建模
• 最小割問題建模
• 最小花費最大流演算法
• 最小花費最大流建模

如果有時間的話

• Misc
• 線性規劃
• 趣題選講

圖論關鍵

• 知識 - 多記結論
• 應變 - 臨場發揮
• 拿紙出來用力畫啊

Maximum Flow

Definition

可行流

想像一下…

• 有水流通過的水管
• 公路的車流
• 網路
  • 水管：輸送自來水到你家
  • 水流：從山上下來，洪水
  • 公路：車子走高速公路
  • 網路：送封包。

這些東西都有這些特性

• 有流的上限
• 不能囤積
• 通常會有起點和終點。
• 而我們會希望能傳輸越多越好！
  • 流的上限：河流暴漲 公路塞車 網速
  • 不能囤：否則淹水 連環車禍 大家按F5
  • s/t: 山上流到山下 過年返鄉
  • 越多：木冊線。

• 來正式定義何謂 s-t cut
• 當然是一張圖
• 流量上限
• 起/終點

• 流量上限
• 反方向流負的
• 不能囤積
• 流量就是出去多少

Example

這些是上限 ， 想像成前面提到的 網路等等。

Example

算一下

• 都沒有超過上限
• 沒囤
• 算流量 講 s出 = t進

Max-Flow Algorithm

Want

流量最大的一個流，也就是最大流！

想法

一點一點慢慢增加流量

增加容量，找「有空的水管」，有空就是還有多的容量找到後應該可以增加一點

這是一開始的狀況，把所有可以流的抓出來

問：可以增加多少流量？

瓶頸會是最小的一條！

圖上那條不見了.

直到有一天流不了。

s 走不到 t

Question: 這樣是否就是一個最大流？

Answer: No!

很簡單的反例, 最大流 2 綠色是流的邊，這些都不能再流了。

再仔細觀察！

還記得流量對稱 : \( f(u, v) = -f(v, u), \; \forall (u, v)\)

其實快對了，一直沒有用到這個條件。

\( -3 < 0 \) ，可以流過去！

• 流 3 過去 ，就是流 -3 回來。
• 只有正向有邊，可以像作 0 流量上限
• 可以流！因為 -3 < 0

多了中間的邊

Question: 考慮負向邊之後，是否就是一個最大流？

Answer: Yes!

沒騙你！

Residual Network

從剛剛我們知道，有剩的邊是關鍵！

在剩餘網路上不斷找路增加流量！

有一個廢到有剩的邊。 你的流量增加，反向減少。

邊的存法

\( f, c, r \) 知其二則剩下一個也可以推出。

其實可能只要記 \( r \) 就好。

初始邊

• 有向圖 \( u \to v \) : \( r(u, v) = c, r(v, u) = 0 \)
• 無向圖 \( (u, v) \) : \( r(u, v) = c, r(v, u) = c \)

結論

不斷的找路徑擴充流量，直到剩餘網路沒有\( s \leadsto t \) 的路徑，就是最大流！

實作

我們先進行一段 C++ Coding 宣導。

邊的表示

寫個 struct

struct Edge {
  int u, v, f, c;
};

Edge e = {1, 2, 3, 4};

pair

typedef pair<int, int> Edge;
Edge e = {1, 2};

存很多邊

寫鍊表

或是用 vector

vector<Edge> E[VMAX];
// u -> v
E[u].PB({v, 1, 2});
// u <-> v
E[u].PB({v, 1, 2});
E[v].PB({u, 1, 2});

反邊

Flow 我們會需要查反邊

vector<Edge> E[VMAX];

#define SZ(a) ((int)(a).size())

E[u].PB({v, 1, 2, SZ(E[v])  });
E[v].PB({u, 1, 2, SZ(E[u])-1});

Auto

C++11 以上

vector<Edge>::iterator it = E[v].begin();

auto it = E[v].begin();

Iterate-for

C++11 以上

for (auto it=E[v].begin(); it!=E[v].end(); it++) {
    int u = *it.u;
}

for (auto u: E[v]) {
}

Bits/stdc++

G++ only

#include <bits/stdc++.h>

Initialize

int a[5] = {0};
int a[5] = {};

int a[5] = {1, 2, 3}; // 1, 2, 3, 0, 0

Lambda function

bool cmp(int i, int j) {
    return i > j;
}
sort(vector.begin(), vector.end(), cmp);

sort(vector.begin(), vector.end(), [](int i, int j) -> bool {
    return i > j;
});

Compare

bool cmp(Edge e1, Edge e2) {
    if (e1.u != e2.u) {
        return e1.u < e2.u;
    }
    return e1.v < e2.v;
}

bool cmp(Edge e1, Edge e2) {
    return tie(e1.u, e1.v) < tie(e2.u, e2.v);
    // Or
    return make_tuple(e1.u, e1.v) < make_tuple(e2.u, e2.v);
}

Tie

tuple<int, int, int> t = {1, 2, 3};
int a, b, c;
tie(a, b, c) = t;

Ford-Fulkerson Algorithm

int f = 0
while (tf = find_path()) {
    f += tf;
}
return f;

看起來很簡單重點是如何 find_path

int find_path(int u = S, int curf = INF) {
    if (u == T) return curf; // Done!

    for (auto &e: E[u]) {
        int v = e.dest, f = e.f, tf;
        if (tf = find_path(v, min(curf, f))) {
           auto rev = e.rev;
           e.f -= tf; 
           ref.f += tf;
           return tf;
        }
    }
    return 0;
}

要找反邊一加一減接下來的演算法都類似

複雜度

沒有保證！

在流量是整數的時候，每次流量至少增加 \( 1 \)， 複雜度 \( \ord{E \abs{f}} \)。

剛剛那個反例就是最糟的情況

Edmonds-Karp Algorithm

int f = 0
while (tf = find_shortest_path()) {
    f += tf;
}
return f;

有差嗎？

只差在 Edmonds-Karp 每次規定找最短的一條擴充路徑。

差多少呢？

差非常多！ 複雜度變成 \( \ord{V E^2} \)不但跟流量大小無關，無理數也會 work ！

Proof

本來 s -> u 的邊慢慢不見變 u -> s，合理

• u 變小，表示 u -> v 擴充 才會讓這邊出來
• 假設 d(u) 3 -> 2 , d(v) 4 -> 1

Proof

• 廢到有剩的那條
• 因為 u -> v , d(u) = 2, d(v) = 3, u <- v, d(u) = 4, +2

Dinic's Algorithm

Edmonds-Karp 的一個小優化。

每次擴充後其實只有一些點的 \( d(v) \) 會變。

一次把所有長度是 \( k \) 的擴充路徑都擴充完。

Details

畫分層圖

複雜度

每次 \( \ord{k E} \)，總共 \( \ord{V^2 E} \)。

一次 sum deg()

最大流的一些例題

裸的最大流，BJ4

把一條路徑想成是一條流

一些常見的建模技巧

• 點容量限制
• 多個 \( s, t \)。
• 無限的容量。

• 點容量 => 拆成 v v'
• 多st => 加 ss tt
• infty => 用很大的數字

二分圖匹配

我們先說一下定義

• 二分圖
• 匹配

• 可以分成兩團的圖
• 選一些不相交的邊

應用

二分圖匹配有不少應用

• 分配任務
• 分發志願序
• 決定動漫結局

• IOI 講師每個人想教哪些，一個課至多一個人
• 每個人填志願

• 某部動畫
• 線就是 x 喜歡 y
• 是二分圖 男/女
• 有同性xx 會變一般圖 難做
• 求他的一個最大匹配

二分圖轉 Flow

• 上面的人全接一條 s -> u
• 下面的人全接一條 u -> t
• 用 s-u u-t 容量 1 來限制

• 把每一個人想做是一單位的流
• 一個點可以補幾單位到附進的點？

• 講混合圖定義

Euler path

Example

有解的條件

觀察一個路徑 \( v_1 \to v_2 \to \cdots \to v_n \)

每一個中間走到的點 \( +2 \) ，兩端 \( +1 \)。

重點

一個有向圖有歐拉迴路的條件是所有點都滿足 \( \deg^+(v) = \deg^-(v) \)，

混合圖呢？

進來 = 出去，合理。

觀察

其實就是要把每一個無向邊都定向成有向圖

最後要求每一個點的 \( \deg^+(v) = \deg^-(v) \)。

• 一個無向邊最後只會走某一個方向

令還沒有算無向邊時 \( \delta(v) = \deg^-(v) - \deg^+(v) \)。

如果我們把一個邊定成 \( u \to v \) 後， \( \delta(u) \gets \delta(u) - 1, \delta(v) \gets \delta(v) + 1 \)。

可以想作一單位的 $\delta$ 從 \( u \) 流到了 \( v \)。

目標： delta(v) = 0

對於那些 \( \delta(v) > 0 \) 的，也就是需要流出 \( \delta(v) \) 的，我們就建 \( s \to v \)。

對於那些 \( \delta(v) < 0 \) 的，同理建 \( v \to t \)。

可以補好補滿 \( \iff \abs{f} = \sum_{\delta(v) > 0} \delta(v) \)

• 要吐流量出來的，就塞一堆水給他。

Minimum cut

Duality

對偶問題

問題常常是一體兩面某個求最大值的問題常常等價於另一個求最小值的問題

• 「你會的問題裡最難的一個」差不多就是「你不會的問題裡最簡單的一個」
• 「最多可以放多少隻蘿莉在 瀚x 旁邊他還能保持理智」 其實就是在問「要陷害 x瀚 去坐牢要擺幾隻蘿莉？」
• 「給你 1000 元你最多可以活多久」跟「你要活一個月至少需要多少錢？」差不多。

第 3. 就是要找最省錢的一種生活方式

那最大流的對偶是什麼呢？

想像一下…

• 高速公路： 哪裡哪裡壅塞，你其它第方開再快也沒有用
• 網路： 光纖 1G ，連 youtube 看直播卡 經過很多線路
• 水管： 有些水管堵住

一個網路的最大流，就是那些被 「堵住」的水管的淨流量。

這些堵住的水管會把點分成兩群。

畫個圖

Definition

割的定義

重點

• s \in S, t \in T
• 算 S->T 的流量合
• 不算 T -> S

而最大流的對偶問題正是最小割。

Example

他們大小相同注意到有多組解, 3, 1 換 v5->t 也行

(1) \( \implies \) (2) 前面講過。

如果有路徑 可以增加流量。反方向沒有證

截流引理

• 想像電流，各截面相同。
• 證明：一個一個點加進去。

(2) \( \implies \) (3)

找所有在剩餘網路上， \( s \) 連的到的點，令其為 \( S \)， 其他點就是 \( T \)。

\( t \) 不在 \(S\) 中。

這個 cut 上的邊都要流滿，否則有路徑。

\( C \leq \abs{f} \)

由截流知 \( \abs{f} \leq C \)

\( \abs{f} = C \)

(3) \( \implies \) (1) 也證完了。

Find a min-cut

這個引理也告訴了我們，找所有在剩餘網路上， \( s \) 連的到的點，令其為 \( S \)， 其他點就為 \( T \)，就恰好是一個 s-t cut。

最小割的一些例題

裸的最小割，BJ4

分兩類問題

先看個例題

分兩類問題

分成要買/不要買的機器，要生產/不要生產的產品。

把要的就分到 \( S \)，不要的就分到 \( T \)。

當然，還是要建模使得求出的答案即是題目要的。

建模方法

• 選 \( u \) 但不選 \( v \) 要花費 \( c \)。
• 選 \( u \) 就一定要選擇 \( v \)。
• 選 \( u \) 要花費 \( c \)。
• 選 \( u \) 會賺到 \( c \)。

回到那一題

• i 產品需 j 機器 , (i -> j) (infty)
• j 機器花費 (j -> t)
• i 產品賺 (s -> i)

Minimum cost Max flow

Definition

最小花費最大流的定義

和最大流時一樣，我們要求一個流量最大的流。

但現在每個邊除了有流量上限以外，還有一個價格 \( k(u, v) \)， 表示每單位流過要付多少錢。

最後總花費是 \[ k(f) = \sum_{f(u, v) > 0} k(u, v) \cdot f(u, v) \]

如何修改前面的使得可以找一個最小花費的最大流？

我們先想剩餘網路要怎麼做修改。

流量應該不變。

那剩餘網路的花費 \( k_{f} (u, v) \) 如何設？

如果在原圖有一條有向邊 \( u \to v \) ， Cost 為 \( k(u, v) \)。

• 順流： 在剩餘網路上流一單位，表示在原來的流上增加一單位。 \[ \implies k_f(u, v) = k(u, v) \]
• 逆流： 在剩餘網路上反著流一單位，表示在原來的流上減少一單位。 \[ \implies k_f(v, u) = -k(v, u) \]

k_f 是剩餘圖上的邊， k 是原來圖上的，不要搞混

一個負環就是花費總合是負的。有負環，加上去，更小！

• 有負環一定是 u1 -> u2 -> u3
• 本來沒有所以大概是 u2 -> u1 擴充
• 原本的 xor 環，更短。

由這兩個引理我們可以知道只要每次都找最短路擴充，直到最大流即可。

只是現在「最短路」並非邊數最少的路徑，而是花費總合最少的路徑！

綠色是 cost

Psuedo Code

int f = 0
while (tf = find_mincost_path()) {
    f += tf;
}
return f;

Finding min-cost path

可以用任何能處理負邊的演算法，如 SPFA。

總複雜度是 \( \ord{SP \cdot \abs{f}} \)。

把一個機器人的工作歷程想做是一個流。

最小花費最大流的一些例題

很多最大流的題目都可以推擴成花費流。

額外的問題

講一下導出子圖，畫個圖舉例

思路

二分搜答案，假設最大密度為 \( k \)。

\[ \abs{E'} - k \abs{V'} \geq 0 \iff \max_{H = (V', E')} \abs{E'} - k \abs{V'} \geq 0 \]

\[ \abs{E'} = \frac{1}{2} \sum_{v \in V'} \deg_H(v) \]

\[ \deg_H(v) = \deg_G(v) - \sum_{\substack{u \notin H \\ (v, u) \in E}} 1 \]

\[ \Leftrightarrow \; - \min_{H = (V', E')} \sum_{v \in V'} \left( \left(2k - \deg_G(v) \right) + \sum_{\substack{u \notin H \\ (v, u) \in E}} 1 \right) \geq 0 \]

分兩類問題！

cost : 2k - deg sum 1 = 選 v 不選 u 就 1 cost

如果有一個路徑 \( v_1 \to v_2 \to v_3 \cdots \)

匹配！

不如先補滿下界。

但有些點的流量就不守恆了，進來的跟出來的差了 \( \delta(v) \)。

有沒有想到混合圖的歐拉回路那一題！

一些和匹配相關的問題

• 最大獨立點集：一個最大的點集 \( V' \) 使得裡面的點都不相鄰。其大小記做 \( I(G) \)。
• 最大匹配數：前面定義過了。其大小記做 \( M(G) \)。
• 最小點覆蓋：最小的一個點集，使得所有的邊都至少與點集裡的一個點相鄰。其大小記做 \( C_v(G) \)。
• 最小邊覆蓋：最小的一個邊集，使得所有的點都至少與邊集裡的 一個邊相鄰。其大小記做 \( C_e(G) \)。

• 互不衝突的點。
• 很像壓紙。

• 點覆蓋的補集就是獨立點集。
• 先找一個最大匹配，補成邊覆蓋。 M + M + V - 2M = V

二分圖的特性

\( M(G) = C_v(G) \)

把點覆蓋轉成 min-cut ！

很不一樣的是這次在 s 表示 (v in X and 不選 v) or (v in Y and 選 v)

從構造的思路開始，要 u -> v 不能同時不選 = 不選 v 就要選 u