题解 P3386 【【模板】二分图匹配

· · 题解

我仔细浏览了一下所有的题解， 发现其中大部分代码实在是太冗余。打算上传一下自己的题解，感觉讲得很清晰，希望管理员大大能够给过，谢谢！！！

如果在当前匹配方案下再也找不到增广路，那么当前匹配就是最大匹配了。 什么？不清楚什么是增广路？自己百度吧。

匈牙利算法流程：

1.从任意一个没有被配对的点x开始，从点x的边中任意选一条边。如果此时点i没有被配对那么配对成功，则找到了一条增广路。如果点i此时已经被配对了，那么可以尝试将点i与其他点配对。如果尝试成功，则找到一条增广路。这里用match[ ]来记录配对关系， 即match[i] = x。 并且将配对数+1。 这个过程我们用dfs来实现。

2.如果配对失败，就从点x的边中重选一条边尝试。直到点x配对成功或尝试完x所有的边。

3.接下来对没有配对的点一一进行配对，直到所有的点都尝试完毕找不到新的增广路。

三步走了解一下

下面来一波代码，代码很短，只有三十行。

#include <bits/stdc++.h>
#define N 1001
using namespace std;
int n, m, e, ans, match[N];
bool a[N][N], vis[N];
bool dfs(int x){
    for (int i = 1; i <= m; i++)
        if (!vis[i] && a[x][i]){
            vis[i] = 1;
            if (!match[i] || dfs(match[i])){
                match[i] = x;
                return 1;
            }
        }
    return 0;
}
int main(){
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        if (v <= m) a[u][v] = 1;
    }
    for (int i = 1; i <= n; i++){
        ans += dfs(i);
        memset(vis, 0, sizeof(vis));
    }
    cout << ans;
    return 0;
}