poj 2195 km算法初步

题意很明显，就是指在一个地图上面有n个人，有n个房间，然后要使得这些人能够到达一个房间，并且移动的步数最短。

看这道题目的人相信应该都是正在学习km算法的人。。

我推荐文库当中的这个资料，说实话，比较精炼，看起来不至于繁琐。。

转载：http://wenku.baidu.com/view/072015d133d4b14e852468a9.html

说说我对km算法的看法吧。。之前一直想要搞清楚这个是什么样的原理，但是现在发现其实观察一下细节你就能发现这个算法的思想，特别是这个定标的设置，说实话我现在也不知道这个的原理是什么，但是基本上我的体会就是讲一个二分图当中的两堆顶点设为X、Y集合，因为是为了求其中的边权值最大的情况，所以只要选出X集合出发的最大的边权，那么记录为lx[i]，表示第i个顶点最大的边权，那么最优解绝对要小于等于lx[i]的所有之和。然后先找大的边权，然后再找次大，一直推下去，到最后一定能找到最优解。我对这个算法感觉就是这样。我明白我差不多只学会小用一下算法，里面的东西肯定还有很多思想要完善，所以自己只能再接再厉了。。。

代码如下：

View Code

 1 #include<iostream>
 2 #include<string.h>
 3 #include<math.h>
 4 #define Inf 0x7fffffff 
 5 #define N 110
 6 using namespace std;
 7 int map[N][N],n,m,man_Count,home_Count;
 8 int lx[N],ly[N],visx[N],visy[N],match[N],lack;
 9 char temp[N];
10 struct node
11 {
12     int x,y;       
13 }home[N],man[N];
14 bool find(int u)
15 {
16      visx[u]=1;
17      for(int i=0;i<home_Count;i++)
18      {
19          if(!visy[i])
20          {
21              int t=map[u][i]-lx[u]-ly[i];
22              if(t==0)
23              {
24                  visy[i]=1;
25                  if(match[i]==-1||find(match[i]))
26                  {
27                     match[i]=u;
28                     return true;
29                  }
30              }
31              else
32              if(lack>t)lack=t;//这个是为找小一条边权做准备
33          }
34      }
35      return false;
36 }
37 void km()
38 {
39        memset(match,-1,sizeof(match));
40        memset(ly,0,sizeof(ly));
41        for(int i=0;i<man_Count;i++)
42        {
43           while(1)//只有找到最好的匹配的时候才能跳出循环
44           {
45              memset(visx,0,sizeof(visx));
46              memset(visy,0,sizeof(visy));
47              lack=Inf;
48              if(find(i))break;
49              for(int i=0;i<man_Count;i++)if(visx[i])lx[i]+=lack;
50              for(int i=0;i<home_Count;i++)if(visy[i])ly[i]-=lack;
51           }
52        }
53        return ;  
54 }
55 int main()
56 {
57    while(scanf("%d%d",&n,&m))
58    {
59       if(n==0&&m==0)break;
60       man_Count=home_Count=0;
61       for(int i=0;i<n;i++)
62       {
63          scanf("%s",temp);
64          for(int j=0;j<m;j++)
65          {
66             if(temp[j]=='H'){home[home_Count].x=i+1;home[home_Count++].y=j+1;}
67             if(temp[j]=='m'){man[man_Count].x=i+1;man[man_Count++].y=j+1;}
68          }
69       }
70       for(int i=0;i<man_Count;i++)
71       {
72          lx[i]=220;
73          for(int j=0;j<home_Count;j++)
74          {
75             map[i][j]=abs(man[i].x-home[j].x)+abs(man[i].y-home[j].y);
76             if(lx[i]>map[i][j])lx[i]=map[i][j];
77          }
78          for(int i=0;i<home_Count;i++)ly[i]=0;
79       }
80       int answer=0;
81       km();
82       for(int i=0;i<home_Count;i++)answer+=map[match[i]][i];
83       printf("%d\n",answer);
84    }
85    return 0;    
86 }