给定一个二分图,其中左半部包含 n1 个点(编号 1∼n1),右半部包含 n2 个点(编号 1∼n2),二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配:给定一个二分图 G,在 G 的一个子图 M 中,M 的边集 {E} 中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配。
二分图的最大匹配:所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配,其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1、 n2 和 m。
接下来 m 行,每行包含两个整数 u 和 v,表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
输出格式
输出一个整数,表示二分图的最大匹配数。
数据范围
1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤105
输入样例:
2 2 4
1 1
1 2
2 1
2 2
输出样例:
2
上面题目将的这么复杂,下面我用简单的例子重新描述一遍
有 n1 个男生和 n2 个女生 (n1 ≤ 500, n2 ≤ 500)。他们之间可以匹配的关系有 m 个 (m ≤ 105)。求最大可能的匹配数。输入格式参考上面。
下面是一位大佬给出的生动而形象例子,通过它可以很好理解该算法的过程
假设现在有一群男同胞和女同胞,而你是这群人中的红娘,现在手上有N1个男同胞,N2个个女同胞,每个人可能对多名异性有好感,有好感在这里用边来表示。如果一对男女互有好感,那么你就可以把这一对撮合在一起;
假如有下面这么一幅图:
现在当作红娘的你,就要尽可能地撮合更过的情侣,此时就用到匈牙利算法的工作模式了
步骤:
我们试着给之前1号女生匹配的男同胞(也就是1号男同胞)另外分配一个妹子。
(黄色表示这条边被临时拆掉)
与1号男同胞相连的第二个女生是2号女生,但是2号女生也有主了,怎么办呢?我们再试着给2号女生的原配重新找个男同胞(这里实际上是一个递归的过程)
此时发现2号男同胞还能找到3号女生,那么之前的问题迎刃而解了,回溯回去
回溯之后的过程应该是下面这种
2号男同胞—3号女主 1号男同胞—2号女主 3号男同胞----1号女主
所以到这里时结果时这样子的
总结一下匈牙利算法核心思想:先得到并不一定是你的,后面匹配的只要有机会就不应该放弃。
也有网友调侃: 先得到可能被绿,后得到的才能把握。
算法实现:
#include
#include
#include
using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
//match[j]=a,表示女孩j的现有配对男友是a
int match[N];
//st[]数组我称为临时预定数组,st[j]=a表示一轮模拟匹配中,女孩j被男孩a预定了。
bool st[N];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 为男同胞 u 找一个对象, (或) u的女朋友被别人预定,给u换一个对象, 如果能找合适, 返回true
int find(int u)
{
// 链表遍历
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j]) // 如果女生没对象
{
st[j] = true; // 将女生 j 预定给男生 x
// 如果女生 j 没有对象, 或者
// 女生 j 在前几轮深搜中已预定有对象,但我们成功给她的对象换了个新对象
if(match[j] == 0 || find(match[j]))
{
match[j] = u;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d%d", &n1, &n2, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
cin >> a >> b;
add(a ,b);
}
int re = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if(find(i)) re ++;
}
cout << re << endl;
return 0;
}