匈牙利算法(二分图匹配)学习笔记

作用:进行二分图最大匹配

可以简单理解为,左面一列男生,右面一列女生,男生只会选择特定的几个女生中的一个在一起,问最多有几对男女可以在一起。

我们举个例子,比如a喜欢 c,d b只喜欢c,那么如果我们最初让a和c在一起,那么b就找不到人了,所以这时候我们要尝试看看a能不能换一个人在一起,然后a换了d,b得到了心仪的c,最后实现最大匹配。

匈牙利算法的核心思想就是,如果a要和b匹配,b已经匹配了,那么就看看,匹配b的人能不能换一个人匹配,将b让出来。

我们可以用一个函数find(x),来进行考虑x是否能找到心仪的人。

mp[i][j]表示i是否心仪j

flg[i]为一个标记,是否在本次匹配中尝试过

folw[i]表示某个妹子是否已经跟某汉子匹配

然后我么只需要在主函数中这样调用即可。

二分图匹配还有很多其他的用途

最小点覆盖问题:

选出最少的点,使所有边的两个端点有至少一个被选择。

我们可以得出,最小点覆盖==最大二分图匹配

最大独立点集问题:

选出尽可能多的点,使得选出的点两两不相连

我们可以得出,最大独立点集 == 点数-最大二分图匹配

最小路径覆盖问题:

选出最少的边,使得其能覆盖原图。(例如poj2594)

若原图存在交点需要先求闭包,可参考本博客poj2594

最小路径覆盖 == 总顶点数-最大匹配数

最大团问题:

最大点集,集合内的任意两点间均相连

最大团 == 原图的补图的最大独立点集

 

发表评论