匈牙利算法

原理

见《进阶指南》第425页。

首先从任意一个未被配对的点u开始，从点u的边中任意选一条边（假设这一条边是u -> v）开始配对。如果此时点v还没有被配对，则配对成功，此时便找到了一条增广路（只不过这条增广路比较简单）。如果此时点v已经被配对了，那就要尝试进行“连锁反应”。如果尝试成功了，则找到一条增广路，此时需要更新原来的配对关系。这里要用一个数组match来记录配对关系，比如点v与点u配对了，就记作match[v] = u。配对成功后，记得要将配对数加1。配对的过程可以通过深度优先搜索来实现，当然广度优先搜索也可以。如果刚才所选的边配对失败,要从点u的边中再重新选一条边，进行尝试，直到点u配对成功，或者尝试过点u所有的边为止。接下来继续对剩下没有被配对的点一一进行配对，直到所有的点都尝试完毕，找不到新的增广路为止。

时间复杂度$O(NM)$。

模板题

洛谷-P3386-【模板】二分图最大匹配

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010, M = 50010;
struct edge {
    int to, next;
};
edge e[2 * M];
int idx, head[N];
int n, m;
int ln, rn;
bool mark[N];
int match[N];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
bool dfs (int cur) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (mark[to] == true) continue;
        mark[to] = true;
        if (match[to] == 0 || dfs(match[to]) == true) {
            match[to] = cur;
            return true;
        }
    }
    return false;
}

int main () {
    memset(head, -1, sizeof(head));
    cin >> ln >> rn >> m;
    n = ln + rn; // 1 ~ ln, ln+1 ~ ln+rn
    for (int i = 1, u, v; i <= m; ++ i) {
        cin >> u >> v;
        add_edge(u, v + ln);
        add_edge(v + ln, u);
    }

    int res = 0;
    for (int i = 1; i <= ln; ++ i) {
        memset(mark, 0, sizeof(mark));
        if (dfs(i) == true) ++ res;
    }
    cout << res << endl;
    return 0;
}