二分图最大匹配总结

时间:2022-11-07 06:31:53

【二分图最大匹配】
极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。

求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)。

二分图最大匹配问题最直观的模型就是:给定两个点集A和B,以及一些边,每条边的两个端点都分别属于A集和B集。我们用一条边将A集的一个点x和B集的一个点y相连,且x和y都无其他相连情况,称为一次匹配。这个问题所求的就是最多的匹配次数。

【匈牙利算法】
匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是二部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

其实也可以理解为有a出去的边连到了b,而b现在被c所占据,所以就要让b腾出空位与a匹配,那么就要让c匹配其他的点,所以从c连出去的边查找是否有匹配的点从而判断b是否可以腾出空位。

【核心代码】
Ps:有两种不同的写法(主要随自己喜好)。

第一种:

bool Find(int x)
{
if (vis[x]) return 0;
vis[x]=1;//遍历过的点打上标记
for (int j=lnk[x]; j; j=nxt[j])
if (!who[son[j]]||Find(who[son[j]])) {who[son[j]]=x; return 1;}//找增广路
return 0;
}

第二种:

bool Find(int x)
{
for (int j=lnk[x]; j; j=nxt[j])
if (!vis[son[j]])
{
vis[son[j]]=1;//给连出去的点打上标记
if (!who[son[j]]||Find(who[son[j]])) {who[son[j]]=x; return 1;}//找增广路
}
return 0;
}

【例题】
bzoj1059
bzoj1191