题目描述
给定一个二分图,其中左半部包含 $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≤10^5$
样例
输入样例:
2 2 4
1 1
1 2
2 1
2 2
输出样例:
2
算法
匈牙利算法
时间复杂度
$O(nm)$
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
// 使用邻接表存储稀疏图
int h[N], e[M], ne[M], idx;
int match[N]; //右边点对应点(妹子匹配的男性)
bool st[N]; // 对左边的某一个点来说, 只搜索右边看上的但一次(不要重复搜索点)
// 匈牙利算法寻找匹配
bool find(int x)
{
// 遍历x的邻接点(x在左边,因此x的邻接点都在右边, 都是(该男生看上的)妹子)
for (int i=h[x]; i!=-1; i=ne[i])
{
int j=e[i];
if (!st[j]) //该男生还没有考虑过j妹子
{
st[j] = true; // 考虑j妹子
if (match[j] == 0 || find(match[j])) // 如果j妹子还没有被匹配 或者匹配j妹子的男生可以换人
{
match[j] = x;
return true;
}
}
}
return false;
}
// 添加边
void add(int a, int b)
{
e[idx] = b, ne[idx]=h[a], h[a] = idx++;
}
int main()
{
scanf("%d%d%d", &n1, &n2, &m);
memset(h, -1, sizeof h);
while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
int res = 0; // 匹配的数量
for (int i=1; i<=n1; i++) // 遍历左边的点(每个男性)
{
memset(st, false, sizeof st); // 妹子清空, 表示左边的第i个男生还没有开始看妹子
if (find(i)) res++; // 找到了
}
printf("%d\n", res);
return 0;
}