Dinic's Algorithm

繼上次的 Ford-Fulkerson 後，這次來研究研究在程式競賽常用的演算法 : Dinic’s Algorithm，如果不知道 Ford-Fulkerson 演算法是什麼，建議先到這裡了解 ~

先說 Dinic’s Algorithm 的核心思想是 :

使用 BFS 建立層次網路
在層次網路的基礎上用 DFS 找一條從源點到匯點的路徑，並計算上面的瓶頸，再更新路徑上的正向和反向邊
繼續執行 2 直到這個層次網路中找不到源點到匯點的路徑，此時找到的加總流量會稱為阻塞流
回到 1 重新建立層次網路

簡單的說，Dinic’s Algorithm 就是每次建立一個層次網路，並在該層網路上尋找阻塞流，重複做這個動作直到匯點無法到達為止

看不懂沒關係，以後懂就好，很明顯地，這裡有 2 個玩意兒需要了解 : 層次網路和阻塞流

我們假設一個長的像下面的圖 :

        s
    10／  ＼ 5
     ↙  5  ↘
    a  ———→ b
  5 ＼     ／ 10
      ↘   ↙
        t

這張圖的故事是這樣的 : 窗戶國和企鵝國長期處於敵對狀態，再特務 00721 的幫助下，兩國決定重新和好，作為和平的象徵兩國決定修建列車軌道連接彼此，s 代表窗戶國 t 代表企鵝國，a 和 b 則是蘋果國和韭菜國 ~~( 硬要掰一個故事出來 )~~

層次網路
#

所謂層次網路指的是利用 BFS 為每個節點標記「層級」，甚麼意思呢 ? 你看從 s 走到 a 和 b 是不是需要走「1 步」 ; 從 s 走到 t 則需要走「2 步」，這裡的「步」就代表從源點 s 到某個點總共經過了多少個「邊」，利用這個方式就可以建立層次網路

第 0 層 : s
第 1 層 : a 、b
第 2 層 : t

值得注意的是 a → b 是成立的，但在建立層次網路中卻會忽略它，因為在下一個步驟的找阻塞流過程中，DFS 會規定只能從 「第 i 層」走到「第 i + 1 層」，因此像 a 、 b 這樣處於同一層的狀態下會把它們間的路徑忽略

阻塞流
#

接下來是找到阻塞流 ( 使用 DFS )，在剛剛建立的層次網路中可以找到下面這兩條路徑 :

s → a → t
s → b → t

需要注意，此時 DFS 只能沿著 Level(u) + 1 = Level(v) 的邊前進，白話來講就是一次只能往下一層走，不能一次大跳 1 層以上

觀察這兩 2 條路線 :

路徑 1 s → a → t
- 瓶頸 : s → a 是 10 ; a → t 是 5，取最小值 5
- 更新殘餘容量 : s → a 剩 5 ; s → t 剩 0
- 目前總流量 : 5
路徑 2 s → b → t
- 瓶頸 : s → b 是 5 ; b → t 是 10，取最小值 5
- 更新殘餘容量 : s → b 剩 0 ; b → t 剩 5
- 目前總流量 : 10

因為找不到其他符合層次規則且有容量的路徑，所以這回合結束

那此時所謂的阻塞流就是最後的總流量 : 10，可以感覺到，阻塞流就是指在「目前層次網路」上所有的最短路線都「塞爆了」( 即容量為 0 )，也因為這樣所以被叫做「阻塞流」

不過注意不要把阻塞流和增廣路徑、最大流搞混了，增廣路徑是指從源點到匯點的那條路 ; 而最大流則是整張圖真正能容納的極限流量，這就像你找到了阻塞流，乍看之下沒有其他路了，但如果允許繞遠路可能還有其他「小巷子」可以到達目的地，所以阻塞流不一定是最大流，目前我們只做了第 1 回合，接下來要繼續第 2 回合，到時候對這個概念會更加了解 ( 應該吧 )

第 2 回合
#

我們回顧一下，這張圖原本長這樣子 :

        s
    10／  ＼ 5
     ↙  5  ↘
    a  ———→ b
  5 ＼     ／ 10
      ↘   ↙
        t

經歷了第一回合的摧殘後，它現在應該變成醬子 :

        s
     5／  ＼ 0
     ↙  5  ↘
    a  ———→ b
  0 ＼     ／ 5
      ↘   ↙
        t

此時總流量是 10 咱們接著進入第 2 回合，首先同樣地，給它建立一個層次網路

第 0 層 : s
第 1 層 : a
第 2 層 : b
第 3 層 : t

你會發現，上次的層次網路只有 3 層，這次重新建立後變成了 4 層

接著我們要找阻塞流，根據建立好的層次網路和一次只走一層的規則，不難發現它只有一條路徑可以走 :

路徑 1 : s → a → b → t
- 瓶頸 : 3 段容量都剛好是 5 ，取最小值 5
- 更新殘餘容量 : 這 3 條邊的剩餘容量全部變為 0
- 目前流量 : 15

第 3 回合
#

經歷前 2 回合的摧殘，現在圖變這樣 :

        s
     0／  ＼ 0
     ↙  0  ↘
    a  ———→ b
  0 ＼     ／ 0
      ↘   ↙
        t

其實也不用看了，因為全部的容量都是 0 這個時候建立層次網路會是 :

第 0 層 : s

所以演算法結束，最大流是 15 ~

程式
#

(程式參考自 claude)


#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 10005;
const long long INF = 1e18;

struct Edge {
    int to, rev;
    long long cap;
};

vector<Edge> graph[MAXN];
int level[MAXN];  // 分層圖
int iter[MAXN];   // 當前弧優化
int n;

// 加邊
void addEdge(int u, int v, long long cap) {
    graph[u].push_back({v, (int)graph[v].size(), cap});
    graph[v].push_back({u, (int)graph[u].size() - 1, 0});
}

// BFS 建立分層圖
bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0;
    q.push(s);
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto &e : graph[v]) {
            if (level[e.to] < 0 && e.cap > 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
    return level[t] >= 0;  // 能到達匯點
}

// DFS 尋找阻塞流
long long dfs(int v, int t, long long f) {
    if (v == t) return f;
    
    for (int &i = iter[v]; i < graph[v].size(); i++) {
        Edge &e = graph[v][i];
        if (level[v] < level[e.to] && e.cap > 0) {
            long long d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                graph[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// Dinic 主函數
long long maxFlow(int s, int t) {
    long long flow = 0;
    while (bfs(s, t)) {
        memset(iter, 0, sizeof(iter));
        long long f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int m, s, t;
    cin >> n >> m >> s >> t;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        long long cap;
        cin >> u >> v >> cap;
        addEdge(u, v, cap);
    }
    
    cout << maxFlow(s, t) << endl;
    
    return 0;
}

輸入輸出
#

輸入格式 :
n m s t          // 節點數、邊數、源點、匯點
u1 v1 cap1       // 邊: u1->v1, 容量 cap1
u2 v2 cap2

輸出 :
最大流

BFS 分層圖
#

這邊直接從程式中的 bfs() 函數來看，前面的 addEdge() 等等可以到這裡了解

bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0;
    q.push(s);
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto &e : graph[v]) {
            if (level[e.to] < 0 && e.cap > 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
    return level[t] >= 0;  // 能到達匯點
}

首先處理 level 這個陣列，在一開始先用 memset 把它的值全部設成 -1 ，我來試著把 level 簡化成這樣 :

index	0	1	2	3	4	5	6	7	8	9
值	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1

在 level 中，index 就是第幾號節點的意思 ( 原本是標記陣列中元素位置的數字 )，而對應的值代表那個節點在哪一層，像是一開始不是有 level[s] = 0 嗎，它的意思是把源點 s 的層級設定為 0，假設源點 s 是 0 號節點好了 :

index	0	1	2	3	4	5	6	7	8	9
值 ( 層數 )	0	-1	-1	-1	-1	-1	-1	-1	-1	-1

再來 level[e.to] = level[v] + 1 就是把 v 連出去的「那個節點」也就是 e.to 的層級設定成 v 的當前層級 + 1 ，我們假設源點的 0 號節點連到 4 和 5 號節點，那麼對應的 level 陣列會長這樣 :

index	0	1	2	3	4	5	6	7	8	9
值 ( 層數 )	0	-1	-1	-1	1	1	-1	-1	-1	-1

剩下的是因為用的是廣度優先搜尋（Breadth-First Search, BFS），所以會需要用到 queue，queue 的特徵是像排隊那樣先進先出，所以每到一個節點就會用 for (auto &e : graph[v]) 把 v 連出去的「邊」透過 q.push(e.to) 也就是把被 v 連到的那個節點塞到 queue 中，接著在 int v = q.front() 和 q.pop() 從 queue 抓一個元素出來處理它，反覆這個動作，直到 queue 被清空

註 : graph 是二維陣列，graph[v] 代表的是節點，graph[v][i] 則是這個節點打出去的第 i 號邊

DFS 找阻塞流
#

指標和參照
#

在開始之前，來簡單介紹一下 C++ 的參照也就是那個傳說中的「Call by reference」，我還記得大一的時候程式設計的老師是這樣告訴我們 : 「只要把參照想成代號就好了」，參照的語法長這樣 :

int n = 5;
int &r = n;

在這幾行程式中 r 就是 n 的代號，而對代號做的影響會一併影響到本體，比如我們把 r 加上 5，那麼本體的 n 也會一起加上 5 ，這時候如果把 n 印出來，會發現 n 的值變成了 10

不過 & 這個符號還有另一個意思比如說 :

int n = 10;
cout << &n;

會發現上面這段程式會輸出像 0x6ffe1c 這樣的 16 進位碼，因為在這個情況下，&n 代表的是 n 這個變數在記憶體中的「門牌號碼」。

另外額外補充一下 C++ 有另一個叫指標的東西，可以理解指標就是一種專門存「門牌號碼」的資料型態，比如說 :

int n = 10;
int * ptr = &n;
cout << *ptr;

以上面程式為例，其中 int * ptr 是宣告一個用來存「int」這種資料型態的「門牌號碼」的指標變數，而後面接的=&n 代表把 n 的「門牌號碼」裝進 ptr 中。

最後 cout << *ptr 會輸出 10 ，因為 ptr 本身是一個指標，如果把它輸出出去會得到像 0x6ffe1c 這樣的 16 進位碼，但若額外加了 * 變成 *ptr 會變成間接取值，會變成那個指標變數存的「門牌號碼」指向的那個地方的資料值，而 ptr 存的是 n 的門牌號碼，所以它會把 n 存的值 : 10 給抓出來

iter 陣列
#

long long dfs(int v, int t, long long f) {
    if (v == t) return f;
    
    for (int &i = iter[v]; i < graph[v].size(); i++) {
        Edge &e = graph[v][i];
        if (level[v] < level[e.to] && e.cap > 0) {
            long long d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                graph[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

想像一下，在同一回合（同一個層次網路）中，我們會執行好幾次 DFS 來尋找阻塞流。

當 DFS 來到節點 v 時，它會檢查 v 所有的對外連線（邊）。假設 v 有 3 條路可以走：

第 1 條路：通往一個死胡同（走到最後發現到不了匯點 t）。
第 2 條路：可以通往匯點 t，但在上一次 DFS 時，這條路的「容量已經被我們用光了」（飽和了）。
第 3 條路：還有容量，且能通往匯點。

如果我們沒有 iter 陣列，每一次 DFS 只要經過節點 v，程式都會從頭開始：先檢查第 1 條路，再檢查第 2 條路，最後才走到第 3 條路。

可以把 iter 陣列想成一個書籤它會記錄「在這一回合的層次網路中，節點 v 的邊，上次檢查到哪裡了？」比如說上次檢查了第 1 條邊，檢查完後 iter 陣列來到 2，這時候就後直接從第 2 個開始。

因為每跑一圈迴圈會希望 iter[v] 的值也增加，因此用了 int &i = iter[v] 這樣後面的 i++ 時，iter[v] 本體的值也會一起被加加

遞迴和減少正向邊、增加反向邊
#

剩下的就是正常找增廣路徑的邏輯，因為用的是 DFS ，DFS 的特徵是一直往更深處去挖，所以這邊用了遞迴的寫法 :

Edge &e = graph[v][i];
if (level[v] < level[e.to] && e.cap > 0) {
    long long d = dfs(e.to, t, min(f, e.cap));
    if (d > 0) {
        e.cap -= d;
        graph[e.to][e.rev].cap += d;
        return d;
    }
}

因為 e.to 代表的是下一個被連接的節點，把它作為參數傳到 dfs() 中就可以實現 DFS 一直往更深處挖的效果

Edge &e = graph[v][i] 這段因為後面需要對 e 做修改，所以用了參照

graph[v] : 代表第 v 號節點
graph[v][i] : 代表第 v 號節點射出去的第 i 號邊

再來是

e.cap -= d 正向邊減掉瓶頸
graph[e.to][e.rev].cap += d 反向邊加上瓶頸，關於 e.rev 的說明可以參考這裡

Dinic 主函數
#

while (bfs(s, t)){} 不斷的建立分層圖，直到沒辦法建立為止
memset(iter, 0, sizeof(iter)) 把 iter 全部設為 0
while ((f = dfs(s, t, INF)) > 0){} 在分層圖的條件下，不斷地找增廣路徑直到找不到為止，最後得到的 flow 就會是阻塞流，而這個地方也造就了為什麼需要一個 iter 陣列，如果沒有 iter 那麼每次呼叫 dfs() 就需要每條路都檢查

long long maxFlow(int s, int t) {
    long long flow = 0;
    while (bfs(s, t)) {
        memset(iter, 0, sizeof(iter));
        long long f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}

Dinic's Algorithm

層次網路
#

阻塞流
#

第 2 回合
#

第 3 回合
#

程式
#

輸入輸出
#

BFS 分層圖
#

DFS 找阻塞流
#

指標和參照
#

iter 陣列
#

遞迴和減少正向邊、增加反向邊
#

Dinic 主函數
#

相關文章

最大流問題 — Ford-Fulkerson 演算法

Uva - 108 Maximum Sum

20251119-ITSA-第 6 題

層次網路 #

阻塞流 #

第 2 回合 #

第 3 回合 #

程式 #

輸入輸出 #

BFS 分層圖 #

DFS 找阻塞流 #

指標和參照 #

iter 陣列 #

遞迴和減少正向邊、增加反向邊 #

Dinic 主函數 #

相關文章

層次網路
#

阻塞流
#

第 2 回合
#

第 3 回合
#

程式
#

輸入輸出
#

BFS 分層圖
#

DFS 找阻塞流
#

指標和參照
#

iter 陣列
#

遞迴和減少正向邊、增加反向邊
#

Dinic 主函數
#