infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
这是一个典型的最大匹配的题目,题目意思是给出一些房子和一些人,每个人到每个房子都有一个相应的代价,最后要求怎么安排这些人,房子和人一一配对,使最后的代价最小。
方法是KM算法,是一个求最大(最小)匹配的一个很强大的算法。不过这种题目还可以用费用流来做。

下面是某牛的对KM算法讲解
http://hi.baidu.com/anonympine/blog/item/3ee64954fe6f6256574e0021.html

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

  以上就是KM算法的基本思路。但是朴素的实现方法,时间复杂度为O(n4)——需要找O(n)次增广路,每次增广最多需要修改O(n)次顶标,每次修改顶标时由于要枚举边来求d值,复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3) 的。我们给每个Y顶点一个“松弛量”函数slack,每次开始找增广路时初始化为无穷大。在寻找增广路的过程中,检查边(i,j)时,如果它不在相等子图 中,则让slack[j]变成原值与A[i]+B[j]-w[i,j]的较小值。这样,在修改顶标时,取所有不在交错树中的Y顶点的slack值中的最小 值作为d值即可。但还要注意一点:修改顶标后,要把所有的slack值都减去d。

Source Code

Problem: 2195
User: lovecanon
Memory: 368K
Time: 0MS
Language: G++
Result: Accepted
下面是2195我的代码:
//algorithm:KM O(n^4)
#include<stdio.h>
#include
<string.h>
#include
<math.h>
#include
<stdlib.h>
struct node{
    
int r,c;
}man[
10001],home[10001];
int r,c,num_of_man,num_of_home,map[101][101],lx[101],ly[101],match[101];
bool visx[101],visy[101];

int dfs(int t){//寻找完备匹配
    int i,tmp;
    visx[t]
=true;
    
for(i=1;i<=num_of_home;i++){
        
if(!visy[i] && lx[t]+ly[i]==map[t][i]){
            tmp
=match[i];
            visy[i]
=true;
            match[i]
=t;
            
if(tmp==0 || dfs(tmp)) return 1;
            match[i]
=tmp;
        } 
    }
    
return 0;
}

int main(){
    
while(scanf("%d%d",&r,&c),r&&c){
        getchar();
        
int i,j,k; char a;
        num_of_home
=0;num_of_man=0;
        
for(i=1;i<=r;i++){//read_data
            for(j=1;j<=c;j++){
                
if((a=getchar())=='m'){
                    man[
++num_of_man].r=i;
                    man[num_of_man].c
=j;
                }
                
else if(a=='H'){
                    home[
++num_of_home].r=i;
                    home[num_of_home].c
=j;
                }
            }
            getchar();
        }
        
//printf("%d %d\n",num_of_man,num_of_home);
        memset(map,0,sizeof(map));
        
for(i=1;i<=num_of_man;i++){
            
for(j=1;j<=num_of_home;j++){
                map[i][j]
=(int )fabs(man[i].r-home[j].r)+(int )fabs(man[i].c-home[j].c);
            }
        }
        memset(lx,
127,sizeof(lx));
        memset(ly,
0,sizeof(ly));
        
for(i=1;i<=num_of_man;i++){
            
for(j=1;j<=num_of_home;j++){
                
if(map[i][j]<lx[i]) lx[i]=map[i][j];//如果是最大权值匹配 则初始值顶标取最大值
            }                                       //若是最小匹配则取最小值
        }
        
//KM algorithm 
        memset(match,0,sizeof(match));
        
for(i=1;i<=num_of_man;i++){//
            while(1){
                memset(visx,
0,sizeof(visx));//清零
                memset(visy,0,sizeof(visy));
                
int min=10000000;
                
if(dfs(i)) break;//寻找完备匹配 
                for(j=1;j<=num_of_man;j++){//找出 min=1000000;x搜索树上y不在搜索树上边
                    if(visx[j])            //找出顶标最大能改进的d值
                    for(k=1;k<=num_of_home;k++){
                        
if(!visy[k] && map[j][k]-lx[j]-ly[k]<min)//基于 lx[i]+ly[j]<=map[i][j] 找出map[j][k]-lx[j]-ly[k]的最小值 d
                            min=map[j][k]-lx[j]-ly[k];           //若是最大匹配则应满足 lx[i]+ly[j]>=map[i][j] 找出
                    }                                            //lx[i]-ly[j]-map[i][j]的最小值 d
                }
                
for(j=1;j<=num_of_man;j++if(visx[j]) lx[j]+=min;//用d来改进搜索树上各点的顶标
                for(j=1;j<=num_of_home;j++if(visy[j]) ly[j]-=min; //
            }
        }
        
int sum=0
        
for(i=1;i<=num_of_home;i++) sum+=map[match[i]][i];
        printf(
"%d\n",sum);  
    }
    
return 0;
}





posted on 2008-11-08 03:28 infinity 阅读(1076) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理