注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 2195  

2009-11-21 16:21:41|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
二分图最佳匹配,经典的KM算法
#include <stdio.h>  
#include <string.h>   
const  int MAXN = 200+5;   
const  int INF = 1000000000;   
int  N;   
int  g[MAXN][MAXN];   
int  pre[MAXN];   
int  lx[MAXN], ly[MAXN], slack[MAXN],man[MAXN][2],ff[MAXN][2];   
bool  visx[MAXN], visy[MAXN];   
int abs(int a){
if(a<0)
 return -a;
return a;
}
bool  dfs(int  t)   
{   
    int i;   
    visx[t] = true;   
    for(i = 0; i < N; i++)   
    {   
        if(visy[i]) continue;   
        int  tmp = lx[t]+ly[i]-g[t][i];   
        if(tmp == 0)   
        {   
            visy[i] = true;   
            if(pre[i] == -1 || dfs(pre[i]))   
            {   
                pre[i] = t;   
                return true;   
            }   
        }   
        else if(slack[i] > tmp)   
        {   
            slack[i] = tmp;   
        }   
    }   
    return false;   
}   
int  KM()   
{   
    int  i, j, k;   
    for(i = 0; i < N; i++)   
        lx[i] = -INF;   
    memset(ly, 0, sizeof(ly));   
    memset(pre, -1, sizeof(pre));   
    for(i = 0; i < N; i++)   
        for(j = 0; j < N; j++)   
            if(lx[i] < g[i][j])   
                lx[i] = g[i][j];   
               
    for(i = 0; i < N; i++)   
    {   
        for(j = 0; j < N; j++) slack[j] = INF;   
        while(1)   
        {   
             memset(visx, false, sizeof(visx));     
           memset(visy, false, sizeof(visy));
            if(dfs(i)) break;   
            int  d = INF;   
            for(j = 0; j < N; j++)   
                if(!visy[j] && 
d > slack[j])   
                    d = slack[j];   
            for(j = 0; j < N; j++)   
            {   
                if(visx[j]) lx[j] -= d;   
                if(visy[j]) ly[j] += d;   
                else slack[j] -= d;   
            } 
        }   
    }   
    int  ans = 0;   
    for(i = 0; i < N; i++)   
    {   
        if(pre[i] != -1)   
            ans -= g[pre[i]][i];   
    }   
    return  ans;   
}  
int main(){
int h,v,mf,mm;
// freopen("1.txt","r",stdin);
scanf("%d%d",&h,&v);
while(h!=0||v!=0){
mm=mf=0;
for(int i=0;i<h;i++)
 for(int j=0;j<v;j++){
   char c;
   scanf("%c",&c);
   while(c!='.'&&c!='H'&&c!='m')
     scanf("%c",&c);
   if(c=='H'){
ff[mf][0]=i;
ff[mf][1]=j;
mf++;
}
if(c=='m'){
man[mm][0]=i;
man[mm][1]=j;
mm++;
}
}
N=mm;
for(int i=0;i<N;i++)
 for(int j=0;j<N;j++)
   g[i][j]=-(abs(man[i][0]-ff[j][0])+abs(man[i][1]-ff[j][1]));
printf("%d\n",KM());
scanf("%d%d",&h,&v);
}
}

  评论这张
 
阅读(1119)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018