二分图的匹配:给定一个二分图 G,在 G 的一个子图 M 中,M 的边集 {E} 中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配。
二分图的最大匹配:所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配,其边数即为最大匹配数。
O(nm)
最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖
int n1, n2; // n1表示第一个集合中的点数,n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; //memset(h, -1, sizeof h);
int match[N]; //存储第二个集合中的每个点当前匹配的第一个集合中的点
bool st[N]; //表示第二个集合中的每个点是否已被遍历
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = 1;
if (!match[j] || find(match[j]))
{
match[j] = x;
return 1;
}
}
}
return 0;
}
int cnt = 0;//求最大匹配数
memset(match, 0, sizeof match);//初始化
for (int i = 1; i <= n1; i++)
{
memset(st, 0, sizeof st);
if (find(i))
{
cnt++;
}
}