匈牙利演算法 Hungarian Algorithm

匈牙利演算法又稱 Kuhn-Munkres 演算法 (簡稱 KM) 是用於尋找二分圖最大權匹配。在打競程時，不常遇到這類題目，就算遇到也算是很好發揮，把問題轉化再套模板即可。然而，其原理卻相當複雜，理解原理後也有利於理解如何轉化匹配類型的題目，因此這篇會把整套原理說明清楚

閱讀之前可以先看前篇三篇匹配與霍爾定理、Kőnig 定理、擴充路徑演算法，有利於了掌握匹配問題的脈絡

最小權點覆蓋 Minimum Weighted Cover

情境 1

有一個農業公司擁有

$n$ 塊玉米田與

$n$ 個加工廠。每一塊田地可以生產的玉米產量各有不同，每一個加工廠的產能也不同。從第

$i$ 塊田地運送到第

$j$ 個加工廠可以賺到

$w_{i,j}$ 元。公司想要找一組好的匹配使獲利最大化

我們可以把他們的關係化成二分圖，田地

$X=\{x_1,x_2,...,x_n\}$、加工廠

$Y=\{y_1,y_2,...,y_n\}$，將獲利

$w_{i,j}$ 作為權重擺在邊

$x_i{y}_j$ 上，這問題就會轉化成二分圖最大權匹配問題

情境 2

承上述情境，有一天政府認為玉米產量過剩，因此希望可以付錢使停止生產與製造。若公司同意不繼續在第

$i$ 塊田地種玉米，那麼政府就會付

$u_i$ 元給公司；若公司同意不繼續在第

$j$ 個加工廠生產產品，那麼政府就會付

$v_j$ 元給公司。如果

$u_i+v_j<w_{i,j}$，則公司會繼續使用邊

$x_i{y}_j$ 來獲利，不會接受政府的錢。為了可以停止生產與製造，政府必須花費

$u_i+v_j\ge w_{i,j}$ 對於所有

$i,j$。政府希望可以最小化

$\sum u_i+\sum v_j$

我們稱這問題是一個最小權點覆蓋問題

權重點覆蓋 Weighted Covering

一組權重覆蓋，是一組標記 (label) 的選擇，分別是

$u_1,u_2,...,u_n$ 與

$v_1,v_2,...,v_n$。這些組選擇會使得

$u_i+v_j\ge w_{i,j}$。而一個覆蓋

$(u,v)$ 的花費 (cost)

$c(u,v)$ 是

$\sum u_i+\sum v_j$。最小權點覆蓋 (minimum weighted cover) 就是指其中最小的花費。對於一個有最大權完美匹配

$M$ 的二分圖來說，設

$w(M)$ 為最大權重，則

$c(u,v)\ge w(M)$

舉例說明

在下圖中，可以看到一張圖有邊權與點權，點權的加總是

$4+8+3+(-2)=13$，而最大匹配權重

$w(M)=6+6=12$。不難發現

$13=c(u,v)\ge w(M)=12$，且

$\{\begin{array}{l}{v}_1+u_1=4+3\ge w_{1,1}=6\\ v_2+u_1=8+3\ge w_{2,1}=9\\ v_2+u_2=8+(-2)\ge w_{2,2}=6\end{array}$

$$
若把

$v_1$ 的數值減少為

$3$，那我們依然會則到

$c(u,v)\ge w(M)$，且

$v_1+u_1\ge w_{1,1}$

$$
當一張圖並沒有點權時，我們可以自由設計點權，使對於所有

$i,j$，

$u_i+v_j\ge w_{i,j}$，且

$c(u,v)\ge w(M)$。在匈牙利演算法當中，我們會運用到這個性質

Egerváry 定理

簡介

Egerváry 定理是 Kőnig 定理的拓展。簡單來說，Jenő Egerváry 引入了權重的概念到 Kőnig 定理當中，因此這兩定理又被稱為 Kőnig-Egerváry 定理

條件

Egerváry 定理必須符合三個條件:

1. 二分圖
2. 非負邊權
3. 存在一個匹配使所有點都被匹配到

Egerváry 定理

對於一張帶邊權的二分圖，若其邊權不為負，且存在一個匹配

$M$ 使所有點都被匹配到 (即完美匹配)，則最小權點覆蓋問題等價於最大權匹配問題

換句話說，有一帶權點覆蓋

$c(u,v)=w(M)$ 若且為若

$M$ 包含了邊

$x_i{y}_j$ 使

$u_i+v_j=w_{i,j}$，在此情況下有最佳解

等效子圖 Equality Subgraph

一張有權二分圖的等效子圖

$G_{u,v}$ 是

$K_{n,n}$ 的生成圖 (即包含所有節點的圖)，其所有邊皆符合

$u_i+v_j=w_{i,j}$。只要我們調整點權，就會產生不同的等效子圖

右圖為左圖的等效子圖

匈牙利演算法 Hungarian Algorithm

有了以上材料，我們可以來說明匈牙利演算法到底如何運行

想法

根據 Egerváry 定理的描述，其實整個演算法要達到的目標僅有兩個:

• 更新連邊，使邊權最大化
• 更新點權，使點權最小化

要達成這些目標，我們需要不斷的調整權重，直到

$c(u,v)=w(M)$

演算法

先定義一個名詞 excess，是指對於

$i,j$，

$u_i+v_j-w_{i,j}$

初始化

令

$(u,v)$ 為一個點覆蓋，使

$u_i=ma{x}_j\{w_{i,j}\}$、

$v_j=0$

迭代

找出等效子圖

$G_{u,v}$ 中的最大匹配

$M$。若

$M$ 是一個完美匹配，則停止迭代，並回傳

$M$ 為最大權完美匹配。否則，令

$Q$ 是在

$G_{u,v}$ 中大小為

$|M|$ 的點覆蓋，再令

$R=X\cap Q$、

$T=Y\cap Q$，又令最小 excess 為

$ϵ=min\{u_i+v_j-w_{i,j}:x_i\in X-R,y_j\in Y-T\}$。將

$x_i\in X-R$ 中的

$u_i$ 減去

$ϵ$，且

$y_j\in T$ 中的

$v_j$ 加上

$ϵ$，然後再次迭代

其中，尋找最大匹配

$M$ 的演算法，可以使用擴充路徑演算法。從另一角度來看，擴充路徑演算法算是匈牙利演算法的子程式

舉例說明

註 : 這邊以下所使用的

$x,y$ 為節點，

$u,v$ 分別為節點

$x,y$ 的點權

首先，將

$v_j$ 設為

$0$。為了要符合

$u_i+v_j\ge w_{i,j}$，我們必須挑選相鄰節點

$x_i$ 最大邊權的邊。換句話說，就是設

$u_i=ma{x}_j\{w_{i,j}\}$

我們可以觀察下圖其中一個節點

$v_1$ 為什麼要選擇

$9$，而不是

$6$。因為選擇

$9$，才會符合

$u_i+v_j\ge w_{i,j}$

$$
接下來下一個步驟，我們需要去找出等效子圖

$G_{u,v}$。並找出等效子圖中的最大匹配

$M$。會發現右圖的最大基數匹配小於

$n$，因此不是最大權匹配，在這種情況需要繼續迭代

$$
我們可以找出大小為

$|M|$ 的獨立集

$Q=\{x_1,x_2,x_3,y_1\}$，其中

$R=\{x_1,x_2,x_3\}$、

$T=\{y_1\}$。由此可以找出

$X-R=\{x_4,x_5\}$、

$Y-T=\{y_2,y_3,y_4,y_5\}$，因此算出

$ϵ=1$。我們將

$X-R=\{x_4,x_5\}$ 的點權減去

$ϵ$、

$T=\{y_1\}$ 的點權加上

$ϵ$，得到下左圖的新權重，以及右圖的新等效子圖與新的匹配。由於此時的匹配並不是完美匹配，我們繼續迭代

可以注意的是，此時的

$\sum u_i+\sum v_j=31$，而

$w(M)=28$

$$
我們可以再找出大小為

$|M|$ 的獨立集

$Q=\{x_1,x_3,y_1,y_2\}$，其中

$R=\{x_1,x_3\}$、

$T=\{y_1,y_2\}$。由此可以找出

$X-R=\{x_2,x_4,x_5\}$、

$Y-T=\{y_3,y_4,y_5\}$，因此算出

$ϵ=2$。我們將

$X-R=\{x_2,x_4,x_5\}$ 的點權減去

$ϵ$、

$T=\{y_1,y_2\}$ 的點權加上

$ϵ$，得到下左圖的新權重，以及右圖的新等效子圖與新的匹配

可以注意到，此時

$\sum u_i+\sum v_j=w(M)=28$。根據 Egerváry 定理，我們已經找到了最大權完美匹配，因此可以停止迭代並回傳答案

程式實作匈牙利演算法

實作主要可以分為原始的

$O(n^4)$ 版跟優化過的

$O(n^3)$ 版
然後又依走訪方法不同分為 DFS 與 BFS 兩種版本
我兩種都放，這樣比較有趣一點

原始算法

這版本是原本尚未經過優化的版本

在實作上，我們可以定義一個

$y$ 的鬆弛量 slack，即為程式碼中的

$\text{sy[ ]}$，且每次開始找擴充路時初始化為無窮大，這樣才能找到最小值。在尋找擴充路的過程中，檢查邊

$x_i{y}_j$ 時，如果它不在等效子圖中，則讓

$\text{slack[j]}$ 變成原值與

$\text{lx[i] + ly[j] - w[i, j]}$ 的較小值。如此一來，

$y$ 節點的 slack 值中的最小值作為

$ϵ$ 值即可

需要注意的是，在運算時，

$Y-T$ 的節點 slack 值都要減去

$ϵ$

int g[MAXN][MAXN], lx[MAXN], ly[MAXN];  // g: 鄰接矩陣, lx, ly: 標記值
int my[MAXN], sy[MAXN], n;              // my: y 的配對點, sy: slack 優化
bool vx[MAXN], vy[MAXN];                // 紀錄 x, y 是否拜訪過

bool dfs(int x) {  // 擴充路徑演算法
    if (vx[x])
        return false;
    vx[x] = true;
    for (int y = 0, excess; y < n; ++y) {
        if (vy[y])
            continue;
        excess = lx[x] + ly[y] - g[x][y];
        if (!excess) {  // excess = 0, 代表找到了匹配邊
            vy[y] = true;
            if (my[y] == -1 || dfs(my[y])) {
                my[y] = x;
                return 1;
            }
        }
        else if (sy[y] > excess)
            sy[y] = excess; // 找最小 excess
    }
    return false;
}

int hungarian() {
    memset(ly, 0, sizeof(int) * n);
    memset(my, -1, sizeof(int) * n);
    for (int x = 0; x < n; ++x) {
        lx[x] = -INF;
        for (int y = 0; y < n; ++y)
            lx[x] = max(lx[x], g[x][y]);  // X 的標記值取每 row 的最大值
    }
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) // 記得清成 INF
            sy[y] = INF;
        
        while (true) {
            memset(vx, 0, sizeof(bool) * n);  // 先將拜訪清單清空
            memset(vy, 0, sizeof(bool) * n);
            if (dfs(x))  // 若找到新的擴充路徑就離開
                break;
            
            // 找出在 X-R 與 Y-T 之間連邊的值中
            // 最小的當作 epsilon
            int epsilon = INF;
            for (int y = 0; y < n; ++y) {
                if (!vy[y])                         
                    epsilon = min(epsilon, sy[y]);  
            }
            
            // 修改 x, y 標記的值 u, v
            for (int j = 0; j < n; ++j) {
                if (vx[j]) // X - R
                    lx[j] -= epsilon;
                if (vy[j]) // T
                    ly[j] += epsilon;
                else // Y - T
                    sy[j] -= epsilon;
            }
        }
    }
    
    // 算答案
    int ans = 0;
    for (int y = 0; y < n; ++y)
        ans += g[my[y]][y];
    return ans;
}

原始算法時間複雜度

• 第一層迴圈執行
  $n$ 次:
  $O(n)$
• 第二層迴圈最多
  $n$ 次:
  $O(n)$
• 擴充路徑演算法 dfs:
  $O(n^2)$

總時間複雜度:

$O(n)\times O(n)\times O(n^2)=O(n^4)$

優化版本

位於修改

$\text{lx, ly, sy}$ 後的地方增加了一個迴圈，用於判斷該次的修改是否產生可行的擴充路徑。對於新增加的

$ϵ=0$ 的邊，若他有機會是擴充路徑的話，會對此邊連向的節點

$y$ 進行 BFS 判斷有沒有擴充路徑

// 變數大概都和上面差不多
typedef long long ll;
int n, mx[MXN], my[MXN], pa[MXN];  // pa: 維護路徑的東西
ll g[MXN][MXN], lx[MXN], ly[MXN], sy[MXN];
bool vx[MXN], vy[MXN];

void init(int _n) {  // 初始化
    n = _n;
    for (int i = 1; i <= n; i++)  // 1-based
        fill(g[i], g[i] + n + 1, 0);
}
void addEdge(int x, int y, ll w) {  // 加邊
    g[x][y] = w;
}
void augment(int y) {  // 把擴充路徑都反轉
    for (int x, z; y; y = z)
        x = pa[y], z = mx[x], my[y] = x, mx[x] = y;
}
void bfs(int st) {
    for (int i = 1; i <= n; ++i)
        sy[i] = INF, vx[i] = vy[i] = false;

    queue<int> q;
    q.push(st);
    while (true) {
        while (q.size()) { // 擴充路徑演算法
            int x = q.front();
            q.pop();
            vx[x] = true;
            for (int y = 1; y <= n; ++y)
                if (!vy[y]) {
                    ll excess = lx[x] + ly[y] - g[x][y];
                    if (!excess) {
                        pa[y] = x;
                        if (!my[y]) {    // 若沒有匹配就代表有擴充路徑
                            augment(y);  // 所以就反轉
                            return;
                        }
                        vy[y] = true, q.push(my[y]);
                    }
                    else if (sy[y] > excess)
                        pa[y] = x, sy[y] = excess;
                }
        }

        // 找出在 X-R 與 Y-T 之間連邊的值中
        // 最小的當作 epsilon
        ll epsilon = INF;
        for (int y = 1; y <= n; ++y)
            if (!vy[y] && epsilon > sy[y])
                epsilon = sy[y];

        // 修改 x, y 標記的值 u, v
        for (int j = 1; j <= n; ++j) {
            if (vx[j])
                lx[j] -= epsilon;
            if (vy[j])
                ly[j] += epsilon;
            else
                sy[j] -= epsilon;
        }

        // 這裡就是他優化奇妙的地方
        for (int y = 1; y <= n; ++y) {
            if (!vy[y] && sy[y] == 0) {
                if (!my[y]) {
                    augment(y);
                    return;
                }
                // 在這裡加進去後只會跑一次反轉路徑
                vy[y] = true, q.push(my[y]);
            }
        }
    }
}

ll hungarian() { 
    fill(mx, mx + n + 1, 0);
    fill(my, my + n + 1, 0);
    fill(ly, ly + n + 1, 0);
    fill(lx, lx + n + 1, -INF);
    for (int x = 1; x <= n; ++x)
        for (int y = 1; y <= n; ++y)
            lx[x] = max(lx[x], g[x][y]);

    for (int x = 1; x <= n; ++x)
        bfs(x);

    ll ans = 0;
    for (int y = 1; y <= n; ++y)
        ans += g[my[y]][y];  // 答案存在 my[]
    return ans;
}

優化版本的時間複雜度

• $\text{for}$ 迴圈執行
  $n$ 次:
  $O(n)$
• 外層
  $\text{while}$ 迴圈最多
  $n$ 次:
  $O(n)$
• 最多
  $n$ 次執行
  $\text{while}$:
  $O(n)$
• 擴充路徑演算法:
  $O(n^2)$

總時間複雜度:

$O(n)\times (O(n)\times O(n)+O(n^2))=O(n^3)$

用矩陣說明匈牙利演算法

因為用圖來看實在太麻煩了，所以我們可以用

$n\times n$ 矩陣來處理匈牙利演算法

註 : 因為中文太複雜了我總是分不清列與行，因此我就用 row 與 column 來說明，以防自己寫錯

如上面例子，我們再來處理一次這張二分圖，但這次使用矩陣來處理

$$
如上圖，我們可以得到以下鄰接矩陣，裡面每一個元素都表示邊權

$w_{i,j}$

$\left[\begin{array}{ccccc}0& 0& 6& 9& 0\\ 0& 6& 1& 0& 0\\ 0& 1& 2& 0& 0\\ 8& 7& 0& 3& 5\\ 6& 0& 0& 0& 3\end{array}\right]$

我們可以定義一個 excess 矩陣

$c_{i,j}$，將每 row 都減去其中的最大值，使每一個元素皆為

$u_i+v_j-w_{i,j}$。此時，

$u=\{9,6,2,8,4\}$、

$v=\{0,0,0,0,0\}$

$c_{i,j}=\left[\begin{array}{ccccc}9& 9& 3& 0& 9\\ 6& 0& 5& 6& 6\\ 2& 1& 0& 2& 2\\ 0& 1& 8& 5& 3\\ 0& 6& 6& 6& 3\end{array}\right]$

如果將 excess 矩陣對照等效子圖

$G_{u,v}$，會發現一組匹配會對應到一個

$0$ 的集合，使此集合沒有兩個

$0$ 共用同一個 row 或 colum，下圖以底線表示匹配邊。建議可以畫一條直線或橫線覆蓋行或列來確認之

畫直線與橫線最少的線條覆蓋所有的

$0$ 之後，會發現直線對應

$T\subset Q$、橫線對應

$R\subset Q$

此時

$u=\{9,6,2,8,6\}$、

$v=\{0,0,0,0,0\}$

$\left[\begin{array}{ccccc}9& 9& 3& 0& 9\\ 6& 0& 5& 6& 6\\ 2& 1& 0& 2& 2\\ 0& 1& 8& 5& 3\\ 0& 6& 6& 6& 3\end{array}\right]⟶\begin{array}{cc}& \begin{array}{cccccc}T& & & & & \end{array}\\ \begin{array}{c}R\\ R\\ R\\ X-R\\ X-R\end{array}& \left[\begin{array}{ccccc}9& 9& 3& \underset{―}{0}& 9\\ 6& \underset{―}{0}& 5& 6& 6\\ 2& 1& \underset{―}{0}& 2& 2\\ 0& 1& 8& 5& 3\\ \underset{―}{0}& 6& 6& 6& 3\end{array}\right]\end{array}$

接下來，藉由直接對照

$c_{i,j}$， 很快就能找出

$ϵ=1$。我們將

$X-R$ 減去

$ϵ$，

$T$ 加上

$ϵ$，便會得到以下矩陣。藉由這個矩陣，我們可以試著用最少的線覆蓋所有

$0$ 的邊權，並找出

$R$ 與

$T$

注意此時的

$u=\{9,6,2,7,5\}$、

$v=\{1,0,0,0,0\}$

$\left[\begin{array}{ccccc}10& 9& 3& 0& 9\\ 7& 0& 5& 6& 6\\ 3& 1& 0& 2& 2\\ 0& 0& 7& 4& 2\\ 0& 5& 5& 5& 2\end{array}\right]⟶\begin{array}{cc}& \begin{array}{ccccc}T& T& & & \end{array}\\ \begin{array}{c}R\\ X-R\\ R\\ X-R\\ X-R\end{array}& \left[\begin{array}{ccccc}10& 9& 3& \underset{―}{0}& 9\\ 7& \underset{―}{0}& 5& 6& 6\\ 3& 1& \underset{―}{0}& 2& 2\\ 0& 0& 7& 4& 2\\ \underset{―}{0}& 5& 5& 5& 2\end{array}\right]\end{array}$

接下來，對

$c_{i,j}$ 再找一次最小 excess，找出

$ϵ=2$。我們將

$X-R$ 減去

$ϵ$，

$T$ 加上

$ϵ$，便會得到以下矩陣。藉由這個矩陣，我們可以試著用最少的線覆蓋所有

$0$ 的邊權，並找出

$R$ 與

$T$

注意此時的

$u=\{9,6,2,5,3\}$、

$v=\{3,2,0,0,0\}$

$\left[\begin{array}{ccccc}12& 11& 3& 0& 9\\ 7& 0& 3& 4& 4\\ 3& 1& 0& 2& 2\\ 0& 0& 5& 2& 0\\ 0& 5& 3& 0& 0\end{array}\right]⟶\begin{array}{cc}& \begin{array}{cccccc}& & T& T& T& \end{array}\\ \begin{array}{c}\\ \\ \\ R\\ R\end{array}& \left[\begin{array}{ccccc}12& 11& 3& \underset{―}{0}& 9\\ 7& \underset{―}{0}& 3& 4& 4\\ 3& 1& \underset{―}{0}& 2& 2\\ 0& 0& 5& 2& \underset{―}{0}\\ \underset{―}{0}& 5& 3& 0& 0\end{array}\right]\end{array}$

到此會發現，已經找到一組

$Q=R\cup T$，使

$|Q|=|M|$，這就代表已經找到一組最大權完美匹配 (即畫底線的邊)，因此我們停止迭代並回傳答案

註 : 如果在網路上搜尋，會發現另一種矩陣的執行方法。另一種方法是先將每 row 的最小值扣除，再將沒有

$0$ 的 column 扣除最小值，接下來再執行減去

$ϵ$ 的步驟。然而，另一種方法並沒有辦法處理

$K_{n,n}$ 有未連邊，也就是邊權為

$0$ 的情況，也就是網路上的方法只能解決二分圖是

$n$-regular 的狀況，且邊權大於

$0$ 的情況。因此，使用本文上述方法才是正確的通用解法

例題說明

題目來源: Codeforces 1107 F. Vasya and Endless Credits
這題根本閱讀題

題目

有人想要不勞而獲買一台車，已知銀行有

$n$ 個貸款方案，每個貸款方案會在一開始給一筆錢

$a_i$，然後接下來

$k_i$ 個月都要扣

$b_i$ 元。然而，這個人可以在存到錢買到車之後就開車烙跑，問說買車的錢最多是多少

限制

$1\le n\le 500$

$1\le a_i,b_i,k_i\le {10}^9$

每一個方案只能使用一次
每個月最多只能最多申請一個方案

題解

根據題目，最多只會有

$n$ 個月，因此找

$n$ 個方案與

$n$ 個月的最大權完美匹配就好了，邊權就是的定義如下面程式碼

程式碼

/* 以上略 */
int main(){
    ll n, a, b, k;
    cin >> n;
    init(n);
    
    for(int i = 1; i <= n; i++){
        cin >> a >> b >> k;
        for(int j = 0; j < n; j++)
            addEdge(i, j + 1, max(0LL, a - min((ll)j, k) * b));
    }
    cout << hungarian() << '\n';
    return 0;
}

常見的二分圖最大完美匹配變化題

二分圖最小權完美匹配

加負號在每一條邊的邊權，即可反轉大小關係。雖然這樣看似違反 Egerváry 定理的限制，但其實很多人寫的程式實作不會因此受影響。如果會影響的話，就抓個最大值來減去所有邊權，這樣依樣可以轉化成可以解的問題

若二分圖為

$K_{n,m}$ 且

$n>m$

在大小為

$m$ 的獨立集補上點與權重為

$0$ 的邊，使

$n=m$。如果要求最大權，則將負權邊設為

$0$

備註

匈牙利演算法是由美國數學家 Harold Kuhn 在 1955 年提出 (參見原文: The Hungarian method for the assignment problem)，會取名「匈牙利」是為了紀念兩位匈牙利數學家 Dénes Kőnig 與 Jenő Egerváry，也就是提出 Kőnig-Egerváry 定理的那兩位數學家，因為這個演算法有很多內容都是基於那兩位匈牙利數學家的貢獻

其中，Dénes Kőnig 曾寫出第一本圖論的書，英譯為 Theory of finite and infinite graphs (書裡面很多表示方法都不是現代圖論會用的，而且圖偏少，沒事不要讀)，可說是現代圖論領域的開山祖之一

在 1957 年數學家 James Munkres (就是寫出那本很經典的 Topology 的那位)，證出匈牙利演算法是

$O(n^4)$，因此此演算法又被稱為 Kuhn-Munkres 演算法。在之後又有人將演算法優化到

$O(n^3)$

從某些角度看來，擴充路徑演算法只是匈牙利演算法的子程式，有許多資料 (中文居多) 會錯誤地將擴充路徑演算法講成匈牙利演算法

題目練習

OnlineJudge 11383 - Golden Tiger Claw (匈牙利演算法觀念裸題)
OnlineJudge 1045 - The Great Wall Game
OnlineJudge 10746 - Crime Wave - The Sequel
OnlineJudge 10888 - Warehouse

---

參考資料

• D.B.West - Introduction to Graph Theory 2/e
• Introduction to Algorithms, Fourth Edition
• 日月卦長的模板庫 - [ Kuhn-Munkres Algorithm ] 二分圖最大權完美匹配KM算法
• 台師大演算法筆記 - matching
• Wikipedia - Hungarian algorithm
• Wikipedia - Kőnig's theorem (graph theory)
• How do we OPTIMALLY assign drivers to riders? (Hungarian Algorithm) | Bipartite Matchings
• OI Wiki 二分图最大权匹配
• 海大競程 - flow and match
• CP-algorithms - Hungarian algorithm for solving the assignment problem
• Sharonwg26 - 匈牙利演算法 (Hungarian Algorithm )
• 14-4: 匈牙利算法 Hungarian Algorithm
• 2qbingxuan - 二分圖最大權匹配

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2025/2/5