匈牙利算法可以求解二分圖的最大匹配問題（二分圖：如果無向圖$G=(V,E)$的所有點可以分為兩個集合$V_1、V_2$，所有的邊都在$V_1$和$V_2$之間，而$V_1$或$V_2$的內部沒有邊，稱$G$是一個二分圖。）。

直接引用例題進行解釋。

例題：情人節

題目描述

溫馨提示：2月14日是第一臺通用計算機在賓夕法尼亞大學誕生的日子，在這個特殊的日子，請多花點時間陪陪你的電腦。

現在有$n$個男孩（$1～n$編號），$m$個女孩（$1～m$編號），如果一對男女之間存在曖昧關系，那么他倆就有可能成為情侶，現在給出$k$對曖昧關系，請問最多可以產生多少對情侶？

輸入描述

第一行三個整數$n,m,k$。$(1\le n,m\le 3\times 10^3,1\le k\le 10^4)$

接下來$k$行，每行表示一個曖昧關系$x,y$，表示男孩$x$和女孩$y$存在曖昧關系。$(1\le x\le n,1\le y\le m)$。

輸出描述

一行輸出結果。

輸入樣例

3 4 5
1 1
1 2
1 3
2 1
3 4

輸出樣例

3

解釋

至多可以產生三對情侶，分別是$[1,3],[2,1],[3,4]$。

匈牙利算法的流程是這樣的：

對訪問到的男孩，如果他的曖昧對象沒有被分配情侶，那么直接將他們兩配對。如果當前訪問到的曖昧對象被分配了對象，那么他會試圖拆開他們，而被訪問的曖昧對象的情侶則會找他其他的曖昧對象試圖進行配對，往復下去，如果能結對，那么皆大歡喜。如果不行，則返回到第一層那里，去看他的下一個曖昧對象是否已經和他人配對。

原理是一個貪心的思想：當一個節點匹配后，不改變他已經匹配的狀態，只可能更換他的匹配對象，從而實現全局的最大匹配。

采用$dfs$來實現。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 9;vector<int> g[N];
//記錄時間戳，防止一次訪問時走重復路徑，
//代替vis的功能，如果使用vis數組則需要多次清空vis數組
int dfn;        
int p[N];
int vis[N];bool dfs(int x)
{for(auto &y : g[x]){//當前男孩已經被訪問過了if(vis[y] == dfn) continue;     vis[y] = dfn;//如果女孩未經匹配或者下一個男孩可以更改匹配對象if(!p[y] || dfs(p[y]))      {p[y] = x;       //進行匹配return true;}}return false;
}void solve()
{int n, m, k; cin >> n >> m >> k;for(int i = 1; i <= k; ++i)     //存圖{int x, y; cin >> x >> y;g[x].push_back(y);}int ans = 0;        //存答案for(int i = 1; i <= n; ++i){dfn++;if(dfs(i)) ans++;}cout << ans << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1;while(_--) solve();return 0;
}

PS：$K\ddot{o}nig$定理：最小點覆蓋數等于最大匹配數。