POJ-2195 Going Home---KM算法求最小权值匹配（存负边）

题目链接：

https://vjudge.net/problem/POJ-2195

题目大意：

给定一个N*M的地图，地图上有若干个man和house，且man与house的数量一致。man每移动一格需花费$1（即单位费用=单位距离），一间house只能入住一个man。现在要求所有的man都入住house，求最小费用。

思路：

KM算法传送门： 理解篇    运用篇

每个man和house建立带权二分图，曼哈顿距离就是边的值，这里要求最小费用，也就是二分图最小权值匹配，但是KM算法求的是二分图最大权值匹配，所以此处用边的负数求最优匹配，求出来的答案的负数就是最小权匹配。

注意：题目说house最多100，但是没有说明man的范围，所以man应该最多100*100。

应该用house为二分图的X部，因为算法复杂度和X部点数有关，所以用点数少的house为X部

因为存的是负数，在预处理X部的顶标值初始化应该是-INF，不能是0

剩下的就是模板啦

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxx =  + ;//house的上限

 const int maxy =  + ;//man的上限

 const int INF = 0x3f3f3f3f;

 int cntx, cnty;//X部的点的数目，Y部点的数目

 bool visx[maxx], visy[maxy];//是否加入增广路

 int wx[maxx], wy[maxy];//顶标值

 int cx[maxx], cy[maxy];//匹配的点

 int minz;//顶标值和边权最小的差值

 int Map[maxx][maxy];//保存边

 bool dfs(int u)

 {

     visx[u] = ;

     for(int v = ; v <= cnty; v++)

     {

         if(!visy[v])//还未加入增广路

         {

             int t = wx[u] + wy[v] - Map[u][v];

             //计算边权和顶标之差，为0表示是相等子图

             if(t == )

             {

                 visy[v] = ;

                 if(cy[v] == - || dfs(cy[v]))//还未匹配或者反向找到增广路

                 {

                     cy[v] = u;

                     cx[u] = v;

                     //cout<<u<<"v"<<v<<endl;

                     return ;

                 }

             }

             else if(t > )minz = min(minz, t);

         }

     }

     return ;

 }

 int KM()

 {

     memset(cx, -, sizeof(cx));

     memset(cy, -, sizeof(cy));

     memset(wx, -INF, sizeof(wx));//注意，这里存的是负边，所以初始化必须是负无穷

     memset(wy, , sizeof(wy));

     for(int i = ; i <= cntx; i++)//预处理出X部的顶标值

     {

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

         {

             wx[i] = max(wx[i], Map[i][j]);

             //cout<<wx[i]<<endl;

         }

     }

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

     {

         while()

         {

             minz = INF;

             memset(visx, , sizeof(visx));

             memset(visy, , sizeof(visy));

             if(dfs(i))break;

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

                 if(visx[j])wx[j] -= minz;

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

                 if(visy[j])wy[j] += minz;

         }

     }

     int ans = ;

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

         if(cx[i] != -)ans += Map[i][cx[i]];

     return ans;

 }

 struct node

 {

     int x, y;

     node(){}

     node(int x, int y):x(x), y(y){}

 };

 node house[maxx], man[maxy];

 char M[][];

 int main()

 {

     int n, m;

     while(cin >> n >> m && (n && m))

     {

         cntx = cnty = ;

         for(int i = ; i < n; i++)//读图

         {

             cin >> M[i];

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

             {

                 if(M[i][j] == 'H')house[++cntx] = node(i, j);

                 else if(M[i][j] == 'm')man[++cnty] = node(i, j);

             }

         }

         for(int i = ; i <= cntx; i++)//建图

         {

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

             {

                 Map[i][j] = -abs(house[i].x - man[j].x) - abs(house[i].y - man[j].y);

             }

         }

         cout<<(-KM())<<endl;

     }

     return ;

 }