# 匈牙利演算法 Hungarian Algorithm
匈牙利演算法又稱 Kuhn-Munkres 演算法 (簡稱 KM) 是用於尋找二分圖最大權匹配。在打競程時，不常遇到這類題目，就算遇到也算是很好發揮，把問題轉化再套模板即可。然而，其原理卻相當複雜，理解原理後也有利於理解如何轉化匹配類型的題目，因此這篇會把整套原理說明清楚
閱讀之前可以先看前篇三篇[匹配與霍爾定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)、[Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)、[擴充路徑演算法](https://hackmd.io/@ShanC/Augmenting-Path-Algorithm)，有利於了掌握匹配問題的脈絡
## 最小權點覆蓋 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} \geq 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} \geq w_{i, j}$。而一個覆蓋 $(u, v)$ 的花費 (cost) $c(u, v)$ 是 $\sum u_i+\sum v_j$。最小權點覆蓋 (minimum weighted cover) 就是指其中最小的花費。對於一個有最大權完美匹配 $M$ 的二分圖來說，設 $w(M)$ 為最大權重，則 $c(u, v) \geq w(M)$
### 舉例說明
在下圖中，可以看到一張圖有邊權與點權，點權的加總是 $4+8+3+(-2)=13$，而最大匹配權重 $w(M)=6+6=12$。不難發現 $13 = c(u, v) \geq w(M)=12$，且 $\begin{cases}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{cases}$
<img src="https://hackmd.io/_uploads/SJZiWgauyg.png" style="margin: 0 auto; display: block; width: 400px">
$~$
若把 $v_1$ 的數值減少為 $3$，那我們依然會得到 $c(u, v) \geq w(M)$，且 $v_1+u_1\ge w_{1,1}$
<img src="https://hackmd.io/_uploads/S1DTMgpdke.png" style="margin: 0 auto; display: block; width: 400px">
$~$
當一張圖並沒有點權時，我們可以自由設計點權，使對於所有 $i, j$， $u_{i}+v_{j} \geq w_{i, j}$，且 $c(u, v) \geq 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}$。只要我們調整點權，就會產生不同的等效子圖
<center class = "half">
<img src="https://hackmd.io/_uploads/Hyn2-LCd1e.png" style="width: 350px">
<img src="https://hackmd.io/_uploads/HkPJzURuJe.png" style="width: 350px">
</center>
<p class="text-center">
右圖為左圖的等效子圖
</p>
## 匈牙利演算法 Hungarian Algorithm
有了以上材料，我們可以來說明匈牙利演算法到底如何運行
### 想法
根據 Egerváry 定理的描述，其實整個演算法要達到的目標僅有兩個:
- 更新連邊，使邊權最大化
- 更新點權，使點權最小化
要達成這些目標，我們需要不斷的調整權重，直到 $c(u, v)=w(M)$
### 演算法
先定義一個名詞 excess，是指對於 $i, j$，$u_i+v_j-w_{i,j}$
#### 初始化
令 $(u, v)$ 為一個點覆蓋，使 $u_{i} = max_{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 為 $\epsilon=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$ 減去 $\epsilon$，且 $y_j\in T$ 中的 $v_j$ 加上 $\epsilon$，然後再次迭代
其中，尋找最大匹配 $M$ 的演算法，可以使用擴充路徑演算法。從另一角度來看，擴充路徑演算法算是匈牙利演算法的子程式
### 舉例說明
註 : 這邊以下所使用的 $x, y$ 為節點， $u, v$ 分別為節點 $x, y$ 的點權
首先，將 $v_j$ 設為 $0$。為了要符合 $u_{i}+v_{j} \geq w_{i, j}$，我們必須挑選相鄰節點 $x_i$ 最大邊權的邊。換句話說，就是設 $u_{i} = max_{j}\{w_{i,j}\}$
我們可以觀察下圖其中一個節點 $v_1$ 為什麼要選擇 $9$，而不是 $6$。因為選擇 $9$，才會符合 $u_{i}+v_{j} \geq w_{i, j}$
<img src="https://hackmd.io/_uploads/H1XLQIAdyx.png" style="margin: 0 auto; display: block; width: 400px">
$~$
接下來下一個步驟，我們需要去找出等效子圖 $G_{u, v}$。並找出等效子圖中的最大匹配 $M$。會發現右圖的最大基數匹配小於 $n$，因此不是最大權匹配，在這種情況需要繼續迭代
<center class = "half">
<img src="https://hackmd.io/_uploads/H1XLQIAdyx.png" style="width: 350px">
<img src="https://hackmd.io/_uploads/B1vL5LCOkx.png" style="width: 350px">
</center>
$~$
我們可以找出大小為 $|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\}$，因此算出 $\epsilon=1$。我們將 $X-R=\{x_4,x_5\}$ 的點權減去 $\epsilon$、$T=\{y_1\}$ 的點權加上 $\epsilon$，得到下左圖的新權重，以及右圖的新等效子圖與新的匹配。由於此時的匹配並不是完美匹配，我們繼續迭代
可以注意的是，此時的 $\sum u_i+\sum v_j=31$，而 $w(M)=28$
<center class = "half">
<img src="https://hackmd.io/_uploads/SJbwxD0_1l.png" style="width: 350px">
<img src="https://hackmd.io/_uploads/rJaIZPAdJg.png" style="width: 350px">
</center>
$~$
我們可以再找出大小為 $|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\}$，因此算出 $\epsilon=2$。我們將 $X-R=\{x_2,x_4,x_5\}$ 的點權減去 $\epsilon$、$T=\{y_1, y_2\}$ 的點權加上 $\epsilon$，得到下左圖的新權重，以及右圖的新等效子圖與新的匹配
可以注意到，此時 $\sum u_i+\sum v_j=w(M)=28$。根據 Egerváry 定理，我們已經找到了最大權完美匹配，因此可以停止迭代並回傳答案
<center class = "half">
<img src="https://hackmd.io/_uploads/S1SU4wRd1g.png" style="width: 350px">
<img src="https://hackmd.io/_uploads/BJVdEvAuJx.png" style="width: 350px">
</center>
## 程式實作匈牙利演算法
實作主要可以分為原始的 $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 值中的最小值作為 $\epsilon$ 值即可
需要注意的是，在運算時，$Y-T$ 的節點 slack 值都要減去 $\epsilon$
```cpp
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}$ 後的地方增加了一個迴圈，用於判斷該次的修改是否產生可行的擴充路徑。對於新增加的 $\epsilon=0$ 的邊，若他有機會是擴充路徑的話，會對此邊連向的節點 $y$ 進行 BFS 判斷有沒有擴充路徑
```cpp
// 變數大概都和上面差不多
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 來說明，以防自己寫錯
如上面例子，我們再來處理一次這張二分圖，但這次使用矩陣來處理
<img src="https://hackmd.io/_uploads/H1XLQIAdyx.png" style="margin: 0 auto; display: block; width: 400px">
$~$
如上圖，我們可以得到以下鄰接矩陣，裡面每一個元素都表示邊權 $w_{i,j}$
$\begin{bmatrix}
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{bmatrix}$
我們可以定義一個 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}=\begin{bmatrix}
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{bmatrix}$
如果將 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\}$
$\begin{bmatrix}
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{bmatrix} \longrightarrow
\begin{array}{cc} &
\begin{array}{ccc} T & ~ & ~ & ~ & ~ &\end{array}
\\
\begin{array}{ccc}
R \\
R \\
R \\
X-R \\
X-R \\
\end{array}
&
\left[\begin{array}{ccc}
9&9&3&\underline{0}&9 \\
6&\underline{0}&5&6&6 \\
2&1&\underline{0}&2&2 \\
0&1&8&5&3 \\
\underline{0}&6&6&6&3
\end{array}
\right]
\end{array}$
接下來，藉由直接對照 $c_{i, j}$， 很快就能找出 $\epsilon=1$。我們將 $X-R$ 減去 $\epsilon$，$T$ 加上 $\epsilon$，便會得到以下矩陣。藉由這個矩陣，我們可以試著用最少的線覆蓋所有 $0$ 的邊權，並找出 $R$ 與 $T$
注意此時的 $u=\{9,6,2,7,5\}$、$v=\{1,0,0,0,0\}$
$\begin{bmatrix}
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{bmatrix}
\longrightarrow
\begin{array}{cc} &
\begin{array}{ccccc} T & T & ~ & ~ & ~ \end{array}
\\
\begin{array}{ccc}
R \\
X-R \\
R \\
X-R \\
X-R \\
\end{array}
&
\left[\begin{array}{ccc}
10&9&3&\underline0&9 \\
7&\underline0&5&6&6 \\
3&1&\underline0&2&2 \\
0&0&7&4&2 \\
\underline0&5&5&5&2
\end{array}
\right]\end{array}$
接下來，對 $c_{i, j}$ 再找一次最小 excess，找出 $\epsilon=2$。我們將 $X-R$ 減去 $\epsilon$，$T$ 加上 $\epsilon$，便會得到以下矩陣。藉由這個矩陣，我們可以試著用最少的線覆蓋所有 $0$ 的邊權，並找出 $R$ 與 $T$
注意此時的 $u=\{9,6,2,5,3\}$、$v=\{3,2,0,0,0\}$
$\begin{bmatrix}
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{bmatrix}
\longrightarrow
\begin{array}{cc} &
\begin{array}{ccccc} & & T & T & T & ~ \end{array}
\\
\begin{array}{ccc}
\\
\\
\\
R \\
R \\
\end{array}
&
\left[\begin{array}{ccc}
12&11&3&\underline0&9 \\
7&\underline0&3&4&4 \\
3&1&\underline0&2&2 \\
0&0&5&2&\underline0 \\
\underline0&5&3&0&0
\end{array}
\right]\end{array}$
到此會發現，已經找到一組 $Q=R\cup T$，使 $|Q|=|M|$，這就代表已經找到一組最大權完美匹配 (即畫底線的邊)，因此我們停止迭代並回傳答案
註 : 如果在網路上搜尋，會發現另一種矩陣的執行方法。另一種方法是先將每 row 的最小值扣除，再將沒有 $0$ 的 column 扣除最小值，接下來再執行減去 $\epsilon$ 的步驟。然而，另一種方法並沒有辦法處理 $K_{n, n}$ 有未連邊，也就是邊權為 $0$ 的情況，也就是網路上的方法只能解決二分圖是 $n$-regular 的狀況，且邊權大於 $0$ 的情況。因此，使用本文上述方法才是正確的通用解法
## 例題說明
題目來源: [Codeforces 1107 F. Vasya and Endless Credits](https://codeforces.com/contest/1107/problem/F)
~~這題根本閱讀題~~
### 題目
有人想要不勞而獲買一台車，已知銀行有 $n$ 個貸款方案，每個貸款方案會在一開始給一筆錢 $a_i$，然後接下來 $k_i$ 個月都要扣 $b_i$ 元。然而，這個人可以在存到錢買到車之後就開車烙跑，問說買車的錢最多是多少
### 限制
$1\le n \le 500$
$1\leq a_i, b_i, k_i \leq 10^9$
每一個方案只能使用一次
每個月最多只能最多申請一個方案
### 題解
根據題目，最多只會有 $n$ 個月，因此找 $n$ 個方案與 $n$ 個月的最大權完美匹配就好了，邊權就是的定義如下面程式碼
### 程式碼
```cpp
/* 以上略 */
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](https://onlinelibrary.wiley.com/doi/10.1002/nav.3800020109))，會取名「匈牙利」是為了紀念兩位匈牙利數學家 [Dénes Kőnig](https://en.wikipedia.org/wiki/D%C3%A9nes_K%C5%91nig) 與 [Jenő Egerváry](https://en.wikipedia.org/wiki/Jen%C5%91_Egerv%C3%A1ry)，也就是提出 Kőnig-Egerváry 定理的那兩位數學家，因為這個演算法有很多內容都是基於那兩位匈牙利數學家的貢獻
其中，Dénes Kőnig 曾寫出第一本圖論的書，英譯為 [Theory of finite and infinite graphs](https://archive.org/details/theoryoffinitein0000koni/page/422/mode/2up) (書裡面很多表示方法都不是現代圖論會用的，而且圖偏少，沒事不要讀)，可說是現代圖論領域的開山祖之一
在 1957 年數學家 [James Munkres](https://en.wikipedia.org/wiki/James_Munkres) (就是寫出那本很經典的 Topology 的那位)，證出匈牙利演算法是 $O(n^4)$，因此此演算法又被稱為 Kuhn-Munkres 演算法。在之後又有人將演算法優化到 $O(n^3)$
從某些角度看來，擴充路徑演算法只是匈牙利演算法的子程式，有許多資料 (中文居多) 會錯誤地將擴充路徑演算法講成匈牙利演算法
## 題目練習
[OnlineJudge 11383 - Golden Tiger Claw](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2378) (匈牙利演算法觀念裸題)
[OnlineJudge 1045 - The Great Wall Game](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3486)
[OnlineJudge 10746 - Crime Wave - The Sequel](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1687)
[OnlineJudge 10888 - Warehouse](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1829)
[ICPC2005 台北站 - Optimal Bus Route Design](https://vjudge.net/problem/UVALive-3353)
[ICPC2015 台北站 - Task Review](https://vjudge.net/problem/UVALive-7463)
[ICPC2007 台北站 - Sightseeing](https://vjudge.net/problem/UVALive-4039)
----
## 參考資料
- D.B.West - Introduction to Graph Theory 2/e
- Introduction to Algorithms, Fourth Edition
- [日月卦長的模板庫 - [ Kuhn-Munkres Algorithm ] 二分圖最大權完美匹配KM算法](https://sunmoon-template.blogspot.com/2016/05/kuhn-munkres-algorithm.html)
- [台師大演算法筆記 - matching](https://web.ntnu.edu.tw/~algo/Matching.html)
- [Wikipedia - Hungarian algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm)
- [Wikipedia - Kőnig's theorem (graph theory)](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory))
- [How do we OPTIMALLY assign drivers to riders? (Hungarian Algorithm) | Bipartite Matchings](https://www.youtube.com/watch?v=T4TrFA39AJU)
- [OI Wiki 二分图最大权匹配](https://oi-wiki.org/graph/graph-matching/bigraph-weight-match/)
- [海大競程 - flow and match](https://hackmd.io/@LeeShoWhaodian/2024flow)
- [CP-algorithms - Hungarian algorithm for solving the assignment problem](https://cp-algorithms.com/graph/hungarian-algorithm.html)
- [Sharonwg26 - 匈牙利演算法 (Hungarian Algorithm )](https://hackmd.io/@SW/BkM2kzbj8/%2FWudWPU1rQiijpxOiDLGy7g)
- [14-4: 匈牙利算法 Hungarian Algorithm](https://youtu.be/bSoZQkxc1Zw?si=rTHJmHnED9F5jlHg)
- [2qbingxuan - 二分圖最大權匹配](https://omeletwithoutegg.github.io/2020/11/16/Maximum-Weight-Bipartite-Matching/)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/2/5
Sign in with Wallet
Connect another wallet