KM算法求二分图最佳匹配

对于具有二部划分( V1, V2 )的加权完全二分图，其中 V1= { x1, x2, x3, ... , xn }， V2= { y1, y2, y3, ... , yn }，边< xi, yj >具有权值 W_{i,j 。}该带权二分图中一个总权值最大的完美匹配，称之为最佳匹配。

 

记 L(x) 表示结点 x 的标记量，如果对于二部图中的任何边，都有 L(x)+ L(y)>= W_x,y，我们称 L 为二部图的可行顶标。

设 G(V,E) 为二部图， G'(V,E') 为二部图的子图。如果对于 G' 中的任何边 满足， L(x)+ L(y)== W_x,y，我们称 G'(V,E') 为 G(V,E) 的等价子图。

 

定理一：设 L 是二部图 G 的可行顶标。若 L 等价子图 G_L 有完美匹配 M，则 M 是 G 的最佳匹配。

证明：由于 G_L 是 G 的等价子图，M 是 G_L 的完美匹配，所以，M 也是 G  的完美匹配。以由于对于匹配 M 的每条边 e ，都有 e∈ E( G_L )，而且 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 求增广路径，得到一个匹配，如图( 红色代表匹配边 )：

 对 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 是为了保证修改后仍满足性质对于边 有 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. 其它情况保持不变。

如此修改后，我们发现对于边，顶标 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

代码：

#include <stdio.h>
#include <stdlib.h>

int const N= 110, inf= 0x7fffffff;
int mat[N][N], match[N], lx[N], ly[N], vx[N], vy[N], n, m;
int slack[N], hx[N], hy[N], mx[N], my[N];
char map[N][N];

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))

void init(){
    for( int i= 0; i< N; ++i ){
        lx[i]= -inf, ly[i]= 0, vx[i]= 0, vy[i]= 0; match[i]= -1;
        
        for( int j= 0; j< N; ++j )
        mat[i][j]= 0;
    }
    int ch= 0, cm= 0;
    for( int i= 0; i< n; ++i )
    for( int j= 0; j< m; ++j ){
        if( map[i][j]== 'H' ) {
            ch++; hx[ch]= i, hy[ch]= j;
        }
        if( map[i][j]== 'm' ){
            cm++; mx[cm]= i, my[cm]= j;
        }
    }
    n= max( ch, cm );
    for( int i= 1; i<= ch; ++i )
    for( int j= 1; j<= cm; ++j ){
        mat[i][j]= abs( hx[i]- mx[j] )+ abs( hy[i]- my[j] );
        mat[i][j]= -mat[i][j];
        lx[i]= max( lx[i], mat[i][j] );
    }
}

int dfs( int u ){
    vx[u]= 1;
    for( int v= 1; v<= n; ++v ){
        int wt= lx[u]+ ly[v]- mat[u][v];
        
        if( !vy[v] && wt== 0 ){
            vy[v]= 1;
            int t= match[v];
            
            if( t== -1 || dfs(t) ){
                match[v]= u; return 1; }
        }
        else slack[v]= min( slack[v], wt );
    }
    return 0;
}

int km(){
    for( int u= 1; u<= n; ++u )
    while( true ){
        for( int i= 0; i<= n; ++i ) vx[i]= 0, vy[i]= 0, slack[i]= inf;
        if( dfs(u) ) break;
        int d= inf;
        for( int i= 1; i<= n; ++i )
        if( !vy[i] ) d= min( d, slack[i] );
        
        for( int i= 1; i<= n; ++i ){
            if( vx[i] ) lx[i]-= d;
            if( vy[i] ) ly[i]+= d; }
    }
    int ans= 0;
    for( int i= 1; i<= n; ++i )ans+= mat[ match[i] ][i];
    
    return -ans;
}

int main(){
    while( scanf("%d%d",&n,&m)!= EOF ){
        if( n== 0 && m== 0 ) return 0;
        
        for( int i= 0; i< n; ++i )
        scanf("%s", map[i] );
        
        init();
        printf("%d\n", km() );
    }
    
    return 0;
}