匈牙利算法—介绍与基本用途_匈牙利算法的实际意义-CSDN博客

　　匈牙利算法应用于二分图（即可以分为两大部分，且个部分内不连接的图）匹配的问题，它的时间复杂度为O（nm）。它的基本原理是增广路。

　　它的用途主要有三：1、单纯二分图匹配；2、最小点覆盖；3、最大独立集。下面，我将一一介绍。

　　一、单纯二分图匹配

　　例题1：

　　有n只公牛和m只母牛，然后每只公牛都可以和几只的母牛配对。在每只公牛只能配对一只母牛的情况下，求能为牛们配对最多多少对？

　　思路：公牛是二分图的一个集合，母牛也是。接着公牛逐一询问母牛，会出现两种情况。1、如果母牛未被匹配，公牛匹配它；2、如果母牛已被匹配，询问母牛的原配公牛能否换另一头母牛匹配。若行，则该公牛可以获得此母牛；反之，该公牛无法得到该母牛。如果该失配公牛问遍了所有母牛，仍然不能找到合适的配偶，则该公牛匹配失败（ans不能+1）。

　　代码：

　　解题关键：构造二分匹配图，找到可连接的线的条件（mp[ ][ ]==true?）。

　　二、最小点覆盖

　　一般考场上的题目极少是纯匈牙利算法，多数会盖上“最小的覆盖”的薄纱。

　　对于求最小点覆盖的题，我们要运用结论：二分图中 最小点覆盖数 = 最大匹配数 ，因此求最小点覆盖的覆盖的题转化为了求最大匹配数的题。

　　例题2：（poj 1325）

　　有两部机器A和B。A机器有n种工作模式0，1，2，3…… n-1 总共n种；B机器有m中工作模式0，1，2，3…… m-1 总共m种。有k个任务，每个任务可以在A机器的某个模式或者B机器的某个模式中完成。A和B机器开始时都默认在0模式，要选择其他模式就要重启一次。求完成k个任务至少需要重启多少次机器。

　　思路：构图：X集合表示A机器的模式编号，Y集合表示B机器的模式编号，如果两个模式能完成的任务相同，则给它们连边，也就是说，任务用边来表示。

　　例题3：（poj 3692）

　　G个女孩，B个男孩，女孩之间相互认识，男孩之间相互认识，某些男孩同女孩之间相互认识，求最大的相互认识的集合的人数。

　　思路：该题棘手于“女孩之间相互认识，男孩之间相互认识”，因为如果就此构图，会出现G集合和B集合内相互连边，不符合二分图的定义，因此，我们得另辟新路来构图。构图：把没有关系的两点连接，反向建图（即建补图）。

　　代码：

　　三、最大独立集

　　有关最大独立集的题，我们如果利用结论：最大独立集 点数= 总点数 - 最小点覆盖 = 总点数 - 最大匹配数  ，就可以用匈牙利算法轻松求解。若要求独立集的数量，可以通过强联通来求。

　　我们来简单说明一下这个结论。最小点覆盖意思是选最少的点，使得所有的边都至少有一个点被选择。这时候我们把这些被选择的点去掉，发现，所有的点不连通了。那这些剩下的点，便构成了一个独立集。由于我们用的是最小点覆盖，选出的点数是尽量少的，因此独立集的点数是尽量大的。

　　如 例题3，它在求“最大的相互认识的集合的人数”其实本质就是求最大独立集点数，所以它的答案（最大独立集点数）= 总人数（总点数）- 不认识人数（最大匹配数）。

　　例题4：（poj 1466）

　　一些女生与男生有浪漫关系，求一个集合中的最大人数，满足这个集合中两两的人不能配对。其中男生与男生间和女神与女生间本就有有浪漫关系。

　　思路：构图：把X集合的人复制到Y集合，如果两个人有浪漫关系，则给他们连边，最后通过 最大独立集点数=总点数-最大匹配数 得到答案，但需注意，此图中的点相当于两个X集合，所以得到的最大匹配数要除以2。

　　文章最后，介绍关于匈牙利算法的一种简单的优化方法：建邻接表。以节省不必要的重复判断，这样可以大大减少时间，但空间可能会有改变，码量要大些。