算法板子：匈牙利算法——二分图的最大匹配

目录

1. 基础概念

                 （1）二分图的概念

                 （2） 匈牙利算法的作用

2. 代码

---

1. 基础概念

（1）二分图的概念

顶点集 V 分为两个集合，且图中每条边依附的两个顶点都分属于这两个子集，也就是第一个集合中的某个点可以对应上第二个集合中的某个点，就是二分图。

（2） 匈牙利算法的作用

把左边的u集合看成一堆男生，右边的v集合看成一堆女生。匈牙利算法就是找到这个二分图中最多有几段恋爱关系，也就是最多有几对男女可以匹配成功。

2. 代码

#include <iostream>
#include <cstring>
using namespace std;const int N = 500 + 10, M = 1e5 + 10;// h[i]接的单链表代表男生i的所有心仪妹子
int h[N], e[M], ne[M], idx;// vis[i]代表妹子i是否被访问过; vis[2]=1代表妹子i被访问过
// match[i]代表妹子i的男朋友是谁; match[2]=2代表妹子2的男朋友是男生2
int vis[N], match[N];// ans存最多有多少段恋爱关系, 也就是最大匹配数量
int ans;// n1代表男生数量, n2代表妹子数量, m代表二分图有几条边
int n1, n2, m;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}// 判断男生u是否可以和心仪妹子匹配成功
bool dfs(int u)
{// 遍历男生u所有的心仪妹子for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];// 如果这个心仪妹子j被访问过, 就跳过if (vis[j]) continue;// 如果没有被访问过, 设置成被访问过vis[j] = 1;// 如果这个心仪妹子j没有男朋友, 或者她的男朋友可以让出她, 则男生u可以和心仪妹子j匹配if (!match[j] || dfs(match[j])){match[j] = u;return true;}}// 如果遍历了所有心仪妹子, 男生u都没有匹配成功, 则男生u匹配失败return false;
}int main()
{cin >> n1 >> n2 >> m;memset(h, -1, sizeof h);// 将男生所有的心仪妹子存起来for (int i = 0; i < m; i ++ ){int a, b;cin >> a >> b;add(a, b);}// 遍历每一个男生for (int i = 1; i <= n1; i ++ ){// 每次枚举一个男生时, 将所有妹子都初始化成未被访问过memset(vis, 0, sizeof vis);// 如果男生i和心仪妹子匹配成功, 匹配数加一if (dfs(i)) ans ++ ;}cout << ans << endl;return 0;
}