匈牙利算法
图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。
思想
中介卖房子
- 问题引入:一个中介有多个客户,手中有多套房可卖。一个客户可以想买多套房,但一套房只能卖给一个客户。
- 问题解决:客户一个一个的选择,当某个客户没房可选时,联系选中这套房的人,协商能否换一套房,如果能则将当前这套房给当前客户,如不能则当前用户买不到房。(这是一个递归过程)
以下代码为一个实例(文本描述)
* 买家[1,2,3,4,5]
* 房子[a,b,c,d,e]
*
* 1->a or 1->b
* 2->a
* 3->c
* 4->c or 4->d
* 5->e
*
* 1->a a房没有被预约,直接与1号买家预约
* 2->a a房被预约了,找到选中a房的买家,进行协商
* 1->b 1号买家还可以选b房,则b房与1号买家预约
* 2->a a房协商成功,a房与2号买家预约
* 3->c c房没有被预约,直接与3号买家预约
* 4->c c房被预约了,找到3号买家协商
* 3->? 3号买家没有其他选择,协商失败
* 4->d 预约c房失败,但房没有被预约,直接与4号买家预约
* 5->e e房没有被预约,直接与5号买家预约
例题
洛谷 P3386 【模板】二分图最大匹配
解题代码如下
#include <bits/stdc++.h>
using namespace std;
int label[510],used[510];
vector<int> adj[50010];
bool dfs(int x) {
int n = adj[x].size();
for (int i = 0; i < n; i++) {
int y = adj[x][i];
if (!label[y]) {
label[y] = 1;
if (!used[y] || dfs(used[y])) {
used[y] = x;
return true;
}
}
}
return false;
}
int main() {
int n, m, e, x, y;
cin >> n >> m >> e;
for (int i = 0; i < e; i++) {
cin >> x >> y;
adj[x].push_back(y);
}
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
label[j] = 0;
}
if (dfs(i))
res++;
}
cout << res << endl;
return 0;
}