一、二分图的最大匹配
-
前提：给定一个二分图，不用你判断是不是二分图，已经明确知道是二分图，让你求它的最大匹配。
-
定义：在一个无向图中，定义一条边覆盖的点为这条边的两个端点。
找到一个边集(S)包含最多的边，使得这个边集覆盖到的所有顶点中的每个顶点只被一条边覆盖。(S)的大小叫做图的最大匹配。
二、匈牙利算法
又名：【月佬算法】,目标：成就更多美满姻缘！
建立有向图(G)，分为二分图的左侧和右侧。 优先选择左侧序号更小的连接可能的边。 对于两个点的目标点“冲突”的时候，采取“协商”的办法。 即序号小的连接可能连接的另一条边。 若“协商”失败，则放弃序号较大的点的边。
概念看的都好绕，实例比较好懂：
你拥有的大概就是下面这样一张关系图，每一条连线都表示互有好感。
本着救人一命，胜造七级浮屠的原则，你想要尽可能地撮合更多的情侣，匈牙利算法的工作模式会教你这样做：
- 先试着给(1)号男生找妹子，发现第一个和他相连的(1)号女生还名花无主，(got it)，连上一条蓝线
- 接着给(2)号男生找妹子，发现第一个和他相连的(2)号女生名花无主，(got it)
- 接下来是(3)号男生，很遗憾(1)号女生已经有主了，怎么办呢？
我们试着给之前(1)号女生匹配的男生（也就是(1)号男生）另外分配一个妹子。(黄色表示这条边被临时拆掉)
与(1)号男生相连的第二个女生是(2)号女生，但是(2)号女生也有主了，怎么办呢？我们再试着给(2)号女生的原配重新找个妹子(注意这个步骤和上面是一样的，这是一个递归的过程)
此时发现(2)号男生还能找到(3)号女生，那么之前的问题迎刃而解了，回溯回去
| (2)号男生可以找(3)号妹子 | (1)号男生可以找(2)号妹子 | (3)号男生可以找(1)号妹子 |
|---|---|---|
 |
 |
 |
所以第3步最后的结果就是：
- 接下来是(4)号男生，很遗憾，按照第三步的节奏我们没法给(4)号男生腾出来一个妹子，我们实在是无能为力了……香吉士同学走好。
三、C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int M = 100010;
int n1, n2; //左边有n1个点，右边有n2个点
int m; //共有m条边
int h[N], e[M], ne[M], idx; //链式前向星
int match[N]; //右边点对应的左边哪个点
bool st[N]; //是不是已经匹配过
int res; //记录结果数值，成功匹配的对数
//链式前向星建图
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
/**
* 功能：为每个男生找妹子
* @param x
* @return
*/
bool find(int x) {
//枚举每一个看上的集合
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) { //如果没有考虑过
//设置已处理过
st[j] = true;
//下面是经典的内容
//j是当前相中的女生
//match[j] == 0:如果j没有匹配过男生
//find(match[j]):如果j的男朋友match[j]可以找其它女生
if (match[j] == 0 || find(match[j])) {
//设置女生j的男朋友是x,x逆袭成功！
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
//优化输入
ios::sync_with_stdio(false);
cin >> n1 >> n2 >> m;
//初始化邻接表
memset(h, -1, sizeof h);
//读入m条边建图
while (m--) {
int a, b;
cin >> a >> b;
//存的是左边指向右边,因为在代码中只找左边进行梳理，不会去遍历右边，所以只存一边
//不必保存右边结点指向左边结点的边
add(a, b);
}
//枚举左侧的每个点
for (int i = 1; i <= n1; i++) {
//表示后来的更牛，它看上的妹子，就会让其它人让出来，都是没有人选择过的状态！
//就是本轮状态标识的作用，而不是全局状态标识
memset(st, false, sizeof st);
//如果有一个男生成功找到一个妹子，那么个数加1
if (find(i)) res++;
}
//输出结果
printf("%d
", res);
return 0;
}