参考网址：http://blog.163.com/suntroop@yeah/blog/static/17012103120115185927194/
对于具有二部划分( V1, V2 )的加权完全二分图，其中 V1= { x1, x2, x3, ... , xn }， V2= { y1, y2, y3, ... , yn }，边< xi, yj >具有权值 W该带权二分图中一个总权值最大的完美匹配，称之为最佳匹配。
记 L(x) 表示结点 x 的标记量，如果对于二部图中的任何边<x,y>，都有 L(x)+ L(y)>= W，我们称 L 为二部图的可行顶标。
设 G(V,E) 为二部图， G'(V,E') 为二部图的子图。如果对于 G' 中的任何边<x,y> 满足， L(x)+ L(y)== W，我们称 G'(V,E') 为 G(V,E) 的等价子图。
定理一：设 L 是二部图 G 的可行顶标。若 L 等价子图 G有完美匹配 M，则 M 是 G 的最佳匹配。
证明：由于 G 是 G 的等价子图，M 是 G 的完美匹配，所以，M 也是 G 的完美匹配。以由于对于匹配 M 的每条边 e ，都有 e∈ E( G )，而且 M 中每条边覆盖每个顶点正好一次，所以
W( M )= ? W(e), e∈ M = ? L(x), x∈ V
另一方面，对于 G 的任何完美匹配 M' 有
W( M' )= ? W(e), e∈ M' <= ? L(x), x∈ V
于是 W( M )>= W( M' )，即 M 是 G 的最优匹配。
由上述定理，我们可以通过来不断修改可行顶标，得到等价子图，从而求出最佳匹配。
就像匈牙利算法一样，我们依次为每一个顶点 i 寻找增广路径，如果寻找增广路径失败，我们就修改相应的可行顶标，来得到增广路径。
如图：
| 1 2 3 |
| 3 2 4 |
| 2 3 5 |
若要对这个完全二分图求最佳匹配
初始化：
Lx(1)= max{ y| w(1,y), 1<= y<= 3 }= max{ 1, 2, 3 }= 3, Ly(1)= 0
Lx(2)= max{ 3, 2, 4 }= 4, Ly(2)= 0
Lx(3)= max{ 2, 3, 5 }= 5, Ly(3)= 0;
我们建立等价子图( 满足 Lx(x)+ Ly(y)== W(x,y) ) 如下：
对于该图，运用匈牙利算法对 X 部顶点 1 求增广路径，得到一个匹配，如图( 红色代表匹配边 )：![二分图匹配之KM求二分图最佳匹配算法-LMLPHP]( "二分图匹配之KM求二分图最佳匹配算法-LMLPHP")
对 X 部顶点 2 求增广路径失败，寻找增广路径的过程为 X 2-> Y 3-> X 1。我们把寻找增广路径失败的 DFS 的交错树中，在 X 部顶点集称之为 S， 在 Y 部的顶点集称之为 T。则 S= { 1, 2 }，T= { 3 }。现在我们就通过修改顶标值来扩大等价子图，如何修改。
1) 我们寻找一个 d 值，使得 d= min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T }，因些，这时 d= min{
Lx(1)+Ly(1)-W(1,1), Lx(1)+Ly(2)-W(1,2), Lx(2)+Ly(1)-W(2,1), Lx(2)+Ly(2)-W(2,2) }=
min{ 3+0- 1, 3+0-2, 4+0-3, 4+0-2 }= min{ 2, 1, 1, 2 }= 1。
寻找最小的 d 是为了保证修改后仍满足性质对于边 <x,y> 有 Lx(x)+ Ly(y)>= W(x,y)。
2) 然后对于顶点 x
1. 如果 x∈ S 则 Lx(x)= Lx(x)- d。
2. 如果 x∈ T 则 Ly(x)= Ly(x)+ d。
3. 其它情况保持不变。
如此修改后，我们发现对于边<x,y>，顶标 Lx(x)+ Ly(y) 的值为
1. Lx(x)- d+ Ly(y)+ d， x∈ S, y∈ T。
2. Lx(x)+ Ly(y)， x? S, y? T。
3. Lx(x)- d+ Ly(y)， x∈ S, y? T。
4. Lx(x)+ Ly(y)+ d， x? S, y∈ T。
易知，修改后对于任何边仍满足 Lx(x)+ Ly(y)>= W(x,y)，并且第三种情况顶标值减少了 d，如此定会使等价子图扩大。
就上例而言: 修改后 Lx(1)= 2, Lx(2)= 3, Lx(3)= 5, Ly(1)= 0, Ly(1)= 0, Ly(2)= 0, Ly(3)= 1。
这时 Lx(2)+Ly(1)=3+0=3= W(2,1)，在等价子图中增加了一条边，等价子图变为：
如此按以上方法，得到等价子图的完美匹配。
另外计算 d 值的时候可以进行一些优化。
定义 slack(y)= min{ (x,y)| Lx(x)+ Ly(y)- W(x,y)，x∈ S, y? T }
这样能在寻找增广路径的时候就顺便将 slack 求出。
Pku 2195 Going Home
Pku Going Home