二分图匹配问题

问题

在一个二分图中,每一个点只能匹配一个点,求这个图中最多能存在多少对匹配上的点。

匈牙利算法

dfs(i) 函数为尝试让 i 进行匹配的函数,如果 i 号点可以进行匹配,则答案 ans++

dfs 函数的原理为:首先对与 i 号点有边的点尝试匹配,如果该点已经被匹配,则尝试让该点匹配的点重新匹配,如果匹配成功,修改该点匹配的点为 i 否则尝试下一个点。

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, m;
bool dfs(int i) {
for(int j = 1; j <= m; j++) {
if(match[i][j] && !use[j]) {
use[j] = true;
if(!result[j] || dfs(result[j])) {
result[j] = i;
return true;
}
}
}
return false;
}
int xiongyali() {
int ans = 0;
for(int i = 1; i <= n; i++) {
memset(use, 0, sizeof(use));
if(dfs(i)) ans++;
}
return ans;
}