Hungarian
Hungarian Algorithm(Kuhn-Munkres)(匈牙利算法)
匈牙利算法又称为KM算法，可以在 \(O(n^3)\) 的时间复杂度内解决二分图最大匹配问题。考虑到二分图中的两个集合中的点并不总是相同，为了能应用KM算法解决二分图的最大权匹配，需要先做如下处理：将两个集合中点数比较少的补点，使得两边点数相同，再将不存在的边权重设为0，这种情况下，问题就转换成 最大权完美匹配问题，从而能应用KM算法求解。是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法，美国数学家哈罗德库恩于1955年提出该算法，之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家柯尼格德内什和艾盖瓦里耶内的工作之上创建起来的。 詹姆斯芒克勒斯于1957年回顾了该算法，并发现它的时间复杂度为(强)多项式时间，此后该算法被称为库恩芒克勒斯算法/芒克勒斯分配算法，原始算法的时间复杂度为 \(O(n^4)\)，但杰克爱德蒙斯与理查德卡普发现可以修改算法达到 \(O(n^3)\) 的时间复杂度。
匈牙利算法寻找最大匹配，就是通过不断寻找原有的匹配M的增广路径，因为找到一条M匹配的增广路径，就意味着一个更大的匹配M'，其恰好比M多一条边。
对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的。
- 二分图：图 \(G=(V,E)\): \(V\)是顶点集，\(E\)是边集，将顶点集合分成两类，每类之间的顶点没有边相连接，只有不同顶点集合的点之间才可以有边相连接。匹配(matching) \(M\subseteq E\) 是一个边集合，使得对于 \(forall v \in V\)，至多只属于M中的一个边。匹配M中的边的个数称为匹配的大小。记作 \(|M|\)。最大匹配(perfect matching) 是一个匹配，使得任何其它的匹配 \(|M'| <=|M|\)。 如果顶点\(v\)是匹配 \(M\)的某个边的端点，则它是匹配的，否则，称为是自由的。
参考链接：
https://zh.wikipedia.org/wiki/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95https://www.youtube.com/watch?v=bSoZQkxc1Zw&list=PLvOO0btloRnsbnIIbX6ywvD8OZUTT0_ID&index=16https://www.cnblogs.com/tomato1001/p/12261037.html