二、KM算法：
二分图最优匹配：对于二分图的每条边都有一个权（非负），要求一种完备匹配方案，使得所有匹配边的权和最大，记做最优完备匹配。（特殊的，当所有边的权为1时，就是最大完备匹配问题）
解二分图最优匹配问题可用穷举的方法，但穷举的效率=n！，所以我们需要更加优秀的算法。
先说一个定理：设M是一个带权完全二分图G的一个完备匹配，给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j) in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j]成立，则M是图G的一个最优匹配。
Kuhn－Munkras算法（即KM算法）流程：
v (1)初始化可行顶标的值
v (2)用匈牙利算法寻找完备匹配
v (3)若未找到完备匹配则修改可行顶标的值
v (4)重复(2)(3)直到找到相等子图的完备匹配为止
KM算法主要就是控制怎样修改可行顶标的策略使得最终可以达到一个完美匹配，首先任意设置可行顶标（如每个X节点的可行顶标设为它出发的所有弧的最大权，Y节点的可行顶标设为0），然后在相等子图中寻找增广路，找到增广路就沿着增广路增广。而如果没有找到增广路呢，那么就考虑所有现在在匈牙利树中的X节点（记为S集合），所有现在在匈牙利树中的Y节点（记为T集合），考察所有一段在S集合，一段在not T集合中的弧，取 delta = min {l(xi)+l(yj)-w(xi,yj) , | xi in S, yj in not T} 。明显的，当我们把所有S集合中的l(xi)减少delta之后，一定会有至少一条属于(S, not T)的边进入相等子图，进而可以继续扩展匈牙利树，为了保证原来属于(S,T )的边不退出相等子图，把所有在T集合中的点的可行顶标增加delta。随后匈牙利树继续扩展，如果新加入匈牙利树的Y节点是未盖点，那么找到增广路，否则把该节点的对应的X匹配点加入匈牙利树继续尝试增广。
复杂度分析：由于在不扩大匹配的情况下每次匈牙利树做如上调整之后至少增加一个元素，因此最多执行n次就可以找到一条增广路，最多需要找n条增广路，故最多执行n^2次修改顶标的操作，而每次修改顶标需要扫描所有弧，这样修改顶标的复杂度就是O(n^2)的，总的复杂度是O(n^4)的。
对于not T的每个元素yj，定义松弛变量slack(yj) =min{l(xi)+l(yj)-w(xi,yj), | xi in S}，很明显每次的delta = min{slack(yj), | yj in not T}，每次增广之后用O(n^2)的时间计算所有点的初始slack，由于生长匈牙利树的时候每条弧的顶标增量相同，因此修改每个slack需要常数时间（注意在修改顶标后和把已盖Y节点对应的X节点加入匈牙利树的时候是需要修改slack的）。这样修改所有slack值时间是O(n)的，每次增广后最多修改n次顶标，那么修改顶标的总时间降为O(n^2)，n次增广的总时间复杂度降为O(n^3)。事实上这样实现之后对于大部分的数据可以比O(n^4)的算法快一倍左右。
利用二分图匹配的匈牙利算法和KM算法，我们可以求解大部分的关于二分图的问题，它们提供了求解最大匹配和最优匹配的有效算法，在具体编程时我们只要多注意优化，我们就可以得出求解这类问题的有效方法，从而可以对这类实际问题进行有效合理的解决。
