随笔-72  评论-126  文章-0  trackbacks-0
今天学了KM算法,用于二分图的完美匹配,以前就遇到过很多次,但是一直都没有花时间去学
学的比较挫,写的是n^4的算法
实际上有m*m*n的算法的
下边几道是完美匹配的题目
http://info.zjfc.edu.cn/acm/problemDetail.aspx?pid=1222 赤裸裸的完美匹配,图都建好了
http://acm.hdu.edu.cn/showproblem.php?pid=1533 这个建图很容易
http://acm.hdu.edu.cn/showproblem.php?pid=2282 这个需要建图

下边是http://acm.hdu.edu.cn/showproblem.php?pid=1533 的AC代码
//////////////////////////////////////////////////////////////////////////
//二分图的完美匹配,Kuhn-Munkras算法
#include<stdio.h>
#include
<math.h>
#include
<string>
#define MAXN 101
//////////////////////////////////////////////////////////////////////////
#define inf 0x7FFFFFFF
int edge[MAXN][MAXN];
int match[MAXN];
bool hash[MAXN][MAXN];
bool xhash[MAXN],yhash[MAXN];
char map[MAXN][MAXN];
int min(int a,int b){return a>b?b:a;}
int max(int a,int b){return a>b?a:b;}
void Scanf(int n,int m,int &l);
bool dfs(int p,int n)//找增广路径
{
    
int i;
    
for(i=0;i<n;i++)
    {
        
if(!yhash[i] && hash[p][i])
        {
            yhash[i] 
= true;
            
int t = match[i];
            
if(t == -1 || dfs(t,n))
            {
                match[i] 
= p;
                
return true;
            }
            
if(t != -1)
                xhash[t] 
= true;
        }
    }
    
return false;
}
void show(int id,int n)
{
    
int i,j;
    
for(i=0;i<n;i++)
    {
        
for(j=0;j<n;j++)
        {
            
if(id)
                printf(
"%d ",edge[i][j]);
            
else
                printf(
"%d ",hash[i][j]);
        }
        puts(
"");
    }
    puts(
"");
}
void KM_Perfect_Match(int n)
{
    
int i,j;
    
int xl[MAXN],yl[MAXN];
    
for(i=0;i<n;i++)
    {
        xl[i] 
= 0;
        yl[i] 
= 0;
        
for(j=0;j<n;j++)
            xl[i] 
= max(xl[i],edge[i][j]);
    }
    
bool perfect = false;
    
while(!perfect)
    {
        
for(i=0;i<n;i++)//现阶段已经匹配的路
        {
            
for(j=0;j<n;j++)
            {
                
if(xl[i] + yl[j] == edge[i][j])
                    hash[i][j] 
= true;
                
else
                    hash[i][j] 
= false;
            }
        }

//        show(0,n);
        int cnt = 0;
        memset(match,
-1,sizeof(match));
        
for(i=0;i<n;i++)//当前的图是否能全部匹配
        {
            memset(xhash,
false,sizeof(xhash));
            memset(yhash,
false,sizeof(yhash));
            
if(dfs(i,n))
                cnt 
++;
            
else
            {
                xhash[i] 
= true;
                
break;
            }
        }
        
if(cnt == n)//没有增广路径
            perfect = true;
        
else
        {
            
int ex = inf;
            
for(i=0;i<n;i++)
            {
                
for(j=0;xhash[i] && j<n;j++)
                {
                    
if(!yhash[j])
                        ex 
= min(ex,xl[i] + yl[j] - edge[i][j]);//找到一条没建的边的最小值
                }
            }
            
for(i=0;i<n;i++)//根据这个边来进行松弛
            {
                
if(xhash[i])
                    xl[i] 
-= ex;
                
if(yhash[i])
                    yl[i] 
+= ex;
            }
        }
    }
}
int main()
{
    
int n,m,l;
    
while(scanf("%d%d",&n,&m))
    {
        
if(n == 0 && m == 0)
            
break;
        Scanf(n,m,l);
        KM_Perfect_Match(l);
        
int mindis = 0;
        
for(int i=0;i<l;i++)
            mindis 
+= edge[match[i]][i];
        printf(
"%d\n",-mindis);
    }
    
return 0;
}

//读入建图
void Scanf(int n,int m,int &l)
{
    
int i,j,l1,l2;
    
struct Point{
        
int x,y;
    }MAN[MAXN],HOUSE[MAXN];
    l1 
= l2 = 0;
    
for(i=0;i<n;i++)
    {
        scanf(
"%s",map[i]);
        
for(j=0;j<m;j++)
        {
            
if(map[i][j]=='m')
            {
                MAN[l1].x 
= i;
                MAN[l1].y 
= j;
                l1 
++;
            }
            
else if(map[i][j]=='H')
            {
                HOUSE[l2].x 
= i;
                HOUSE[l2].y 
= j;
                l2 
++;
            }
        }
    }
    l 
= l1;
    
for(i=0;i<l;i++)
        
for(j=0;j<l;j++)
            edge[i][j] 
= -abs(MAN[i].x - HOUSE[j].x) - abs(MAN[i].y - HOUSE[j].y);
}

posted on 2009-04-21 14:32 shǎ崽 阅读(1631) 评论(2)  编辑 收藏 引用

评论:
# re: 二分图的完美匹配 2009-04-24 18:48 | wswyb001
好长啊,还没有学KM  回复  更多评论
  
# re: 二分图的完美匹配 2009-04-28 14:42 | shǎ崽
@wswyb001
这个是n^4的算法
浙大模板n^3的,现在用那个。。。  回复  更多评论
  

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