KM 算法是通过给每个顶点一个标号(叫做顶标)来把求最大权匹配的
问题转化为求完备匹配的问题的。设顶点 Xi 的顶标为 A[i] ,顶点 Yi 的
顶标为 B[i] ,顶点 Xi 与 Yj 之间的边权为 w[i,j] 。在算法执行过程中的任
一时刻,对于任一条边 (i,j) , A[i]+B[j]>=w[i,j] 始终6成立。 KM 算法的正
确性基于以下定理:
6 若由二分图中所有满足 A[i]+B[j]=w[i,j] 的边 (i,j) 构成的子图(称做
相等子图)有完备匹配,那么这个完备匹配就是二分图的最大权匹配。
6 初始时为了使 A[i]+B[j]>=w[i,j] 恒成立,令 A[i] 为所有与顶点 Xi 关
联的边的最大权, B[j]=0 。如果当前的相等子图没有完备匹配,就按下
面的方法修改顶标以使扩大相等子图,直到相等子图具有完备匹配为
止。
6 我们求当前相等子图的完备匹配失败了,是因为对于某个 X 顶点,
我们找不到一条从它出发的交错路。这时我们获得了一棵交错树,它的
叶子结点全部是 X 顶点。现在我们把交错树中 X 顶点的顶标全都减小某
个值 d , Y 顶点的顶标全都增加同一个值 d.
d = min{ A[i]+B[j]-w[i,j] | Xi 在交错树中, Yi 不在交错树中6 }