二分图最大匹配（匈牙利算法）

二分图的匹配：给定一个二分图G，在G中的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数和即为最大匹配数。

匈牙利算法求二分图最大匹配的思想很简单，就是相当于一个一个尝试每一条边，尽可能地增加匹配数，举个例子：

以这个图为例进行讲解匈牙利算法的思想，我们先让左半部的1号节点进行匹配，按照顺序他会和右半部的1号节点进行匹配，同理左半部的2号节点会和右半部的3号节点进行匹配，左半部的3号节点会和右半部的2号节点进行匹配，轮到左半部的4号节点进行匹配时会发现右半部的2号节点已经与左半部的3号节点匹配成功，所以这个时候就要尝试让左半部的3号节点换一个匹配对象，这个时候左半部的3号节点会选择与右半部的4号节点进行匹配，这个时候右半部的2号节点就空出来了，就可以和左半部的4号节点进行匹配了，所以对应的最大匹配数就是4，这也就是一个逐步尝试的过程，其实正好对应着深搜的过程。

因为右半部是一个被匹配的过程，所以我们只需要用一个match[i]记录右半部的i号节点所匹配的左半部的节点编号即可，如果match[i]=0说明右半部的i号节点还没有进行匹配。

思路明白了，代码就比较容易实现，下面给出一道例题：

题目链接：【模板】二分图最大匹配 - 洛谷

输入样例：

4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1

 输出样例：

2

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int N=1e5+10;
int h[N],ne[N],e[N],idx;
int match[N];//match[i]记录与右半部i号节点相匹配的左半部的节点编号 
bool vis[N];//vis[i]标记右半部的i号节点有没有被考虑过 
void add(int x,int y)
{
	e[idx]=y;
	ne[idx]=h[x];
	h[x]=idx++;
}
bool find(int x)
{
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(vis[j]) continue;
		vis[j]=true;
		if(match[j]==0||find(match[j]))
		{
			match[j]=x;
			return true;
		}
	}
	return false;
}
int main()
{
	int n1,n2,m;
	cin>>n1>>n2>>m;
	int u,v;
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		//因为只需要从左半部向右半部进行匹配，所以只需要加单向边 
		add(u,v);
	}
	int ans=0;
	for(int i=1;i<=n1;i++)
	{
		//每个右半部的点都只会被尝试一次，所以每次都需要初始化 
		memset(vis,false,sizeof vis);
		if(find(i)) ans++;
	}
	cout<<ans;
	return 0;
}

最后再给大家稍微提一下最小点覆盖问题，这个问题也是可以利用匈牙利算法来解决的。

最小点覆盖问题就是我们想找到最少的一些点，使得二分图中所有的边的两个顶点至少有一个在这些点之中。

这里就不详细介绍了，直接给大家说出个结论就够用了。

一个二分图中的最大匹配数等于这个图中的最小点覆盖数。