匈牙利算法 二分图的最大匹配

匈牙利算法

图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

思想

中介卖房子

  1. 问题引入:一个中介有多个客户,手中有多套房可卖。一个客户可以想买多套房,但一套房只能卖给一个客户。
  2. 问题解决:客户一个一个的选择,当某个客户没房可选时,联系选中这套房的人,协商能否换一套房,如果能则将当前这套房给当前客户,如不能则当前用户买不到房。(这是一个递归过程)

以下代码为一个实例(文本描述)

 * 买家[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;
}
上一篇:LM2596S-ADJ 程控电压源


下一篇:基于C++的带权重的无向图的实现(邻接表法)