poj 2195 Going Home (km算法)

题目链接：

　　http://poj.org/problem?id=2195

解题思路：

　　把man和home都提取出来，然后算出每个man和home的距离算出来，然后建立匹配图，套用km算法的模板，求最小权值匹配，km模板一般是求最大权匹配，求最小的话，一般是取负，当然如果感觉取负逼格太low，也可以用下面的办法，改进模板。

代码：

 //写的代码太菜，不懂建立匹配图的时候为什么下表从零开始就会使劲wa，但是改成1就会ac，有看出来的小伙伴们请大声说出来，跪谢！！！！！

 //KM算法求完备匹配下的最小权匹配

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 #define maxn 110

 #define INF 0x3f3f3f3f

 int map[maxn][maxn]/*匹配图*/;

 int used[maxn]/*x与y的匹配值*/;

 int  s[maxn]/*修改量*/;

 int n, m;

 int lx[maxn], ly[maxn];/*顶标*/

 int visx[maxn], visy[maxn];

 struct node

 {

     int x, y;

     void init(int xx, int yy)

     {

         x = xx;

         y = yy;

     }

 };

 int Fas(int x, int y)

 {

     if (x > y)

         return x - y;

     return y - x;

 }

 int find (int x)

 {//匈牙利算法，增广路经，扩大相等子图

     visx[x] = ;

     for (int i=; i<n; i++)

     {

         if (!visy[i] && lx[x]+ly[i] == map[x][i])

         {

             visy[i] = ;

             if (!used[i] || find(used[i]))

             {

                 used[i] = x;

                 return ;

             }

         }

         else

             //s[i] = min (s[i], lx[x] + ly[i] - map[x][i]);

             //最大权匹配

             s[i] = min (s[i], map[x][i] - (lx[x] + ly[i]));//更新修改值，保证最小，使求得的结果最优

     }

     return ;

 }

 int KM()

 {

     memset (used, , sizeof(used));

     memset (ly, , sizeof(ly));

     for (int i=; i<n; i++)//初始化顶标

         lx[i] = INF;//lx[i] = 0;最大权匹配

     for (int i=; i<n; i++)

         for (int j=; j<n; j++)

             lx[i] = min(lx[i], map[i][j]);

     for (int i=; i<n; i++)

     {

         for (int j=; j<n; j++)

             s[j] = INF;

         while ()

         {

             memset (visx, , sizeof(visx));

             memset (visy, , sizeof(visy));

             if (find(i))

                 break;

             int num = INF;

             for (int j=; j<n; j++)

                 if (!visy[j])//

                 num = min (num, s[j]);

             for (int j=; j<n; j++)

             {

                 if (visx[j])

                     lx[j] += num;//lx[j] -= num;最大权匹配

                 if (visy[j])

                     ly[j] -= num;//ly[j] += num;最大权匹配

                 else

                     s[j] -= num;

             }

         }

     }

     int res = ;

     for (int i=; i<n; i++)

         res += map[used[i]][i];

     return res;

 }

 int main ()

 {

     char str[maxn];

     int a, b;

     node home[maxn], man[maxn];

     while (scanf ("%d %d", &a, &b), a+b)

     {

         n = m = ;

        memset (map, , sizeof(map));

         for (int i=; i<a; i++)

         {

             scanf ("%s", str);

             for (int j=; str[j]; j++)

             {

                 if (str[j] == 'H')

                     home[n++].init(i, j);

                 if (str[j] == 'm')

                     man[m++].init(i, j);

             }

         }

         for (int i=; i<n; i++)

             for (int j=; j<m; j++)

             map[i][j] = Fas(home[i].x , man[j].x) + Fas(home[i].y , man[j].y);

         printf ("%d\n", KM());

     }

     return ;

 }