二分图最大匹配

1.定义

将一个图的顶点分成两个不相交的集合，使得图中的每一条边都连接这两个集合中的顶点

最大匹配是指找到一个边的集合，其中任意两条边都没有公共顶点，并且这个集合中的边数是最多的

完备匹配即指所有的点均可以被划分如其中一个集合

---

2.匈牙利算法及其实现

我们补充一个定义：增广路指连接两个未匹配顶点且边在匹配集M与非匹配集间交替出现的路径，其两个端点都不与M中的边关联

当一张图为二分图最大匹配时，当且仅当该图不存在增广路

例如下面的链接$1->3->4->6$的这条路径就是增广路(红边指原本进入二分图匹配中的边，黑边为未进入的边)

分析一下易得增广路的长度一定为奇数且红黑边交替出现，黑边数量比红边多一个

于是我们可以贪心的想到每次将增广路上的红边删除，然后加上所有黑边这样我们就可以使答案增加$1$

匈牙利算法就是可以通过找寻增广路来得到二分图最大匹配，每次尝试寻找一条增广路并记录最后通过寻找到的增广路数量确定匹配数

具体实现如下

int T[N];//时间戳防重复访问
int match[N];//指匹配对应的点

bool Hungary( int p,int t )
{
	if( T[p] == t ) QAQ false;//已经访问过这个点，无解
	T[p]=t;//打时间戳
	for( auto &x:rode[p] ) if( !match[x] || Hungary( match[x],t ) )//要么是一个未匹配点，要么继续寻找增广路
	{ match[x]=p; QAQ true; }
	QAQ false;
}

for( int i=1;i<=n;i++ ) ans+=Hungary( i,i );

---

3.时间复杂度

易得最劣情况下每次找增广路我们都会遍历整张图，时间复杂度是趋于暴力的$O(nm)$

---

4.补充

二分图最大匹配问题可以归约为最大流问题，这个在后面的费用流里面会再次提及

届时我们会有$O(\sqrt nm )$甚至是线性的时间复杂度更优秀的算法