Going Home(回家)（标签：二部图，匈牙利算法，KM算法）
题目描述
在网格地图上，有n个男人和n个房屋。 在每个单位时间内，每个小人都可以水平或垂直移动一个单位步长到相邻的点。 对于每个小人，您需要为他移动的每一步支付$ 1的旅行费，直到他进入房屋。 每个房子只能容纳一个小人。
您的任务是计算您需要支付的最低金额，以便将这n个小人送入这n个不同的房子。 输入是方案图，“.”表示空白处，“ H”表示该点上的房屋，而“ m”表示该点上有一个小人。
您的任务是计算您需要支付的最低金额，以便将这n个小人送入这n个不同的房子。 输入是方案图，“.”表示空白处，“ H”表示该点上的房屋，而“ m”表示该点上有一个小人。
您可以将栅格地图上的每个点都视为一个很大的正方形，因此它可以同时容纳n个矮个子。 同样，如果一个小男人跨进带有房屋的网格而不进入该房屋也可以。
Input
输入中有一个或多个测试用例。 每种情况都从给出两个整数N和M的行开始，其中N是地图的行数，M是列数。 输入的其余部分将是描述地图的N行。 您可以假设N和M都在2到100之间（含2和100）。 地图上的“ H”和“ m”数量相同； 最多将有100所房屋。 N和M的输入将以0 0终止。
Output
对于每个测试用例，需要输出一个单个整数，这是您需要付的最小金额（以美元为单位）。
Sample Input
2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0
Sample Output
2
10
28
解题思路
对于此题，看起来十分复杂，没有思路，但是如果你了解二部图以及相关算法，这个题目可以直接套模板解决。我在网络上经过了仔细的查找，发现两篇不错的博文，使用了简单易懂的例子，讲的特别清晰，如下：
- 二部图的定义、匈牙利算法：https://zhuanlan.zhihu.com/p/96229700
- KM算法：https://www.cnblogs.com/wenruo/p/5264235.html
本题目需要用到的是KM算法，但是，其基础是匈牙利算法，所以，如果大家不理解匈牙利算法应该先看第一篇博文。
上文中，讲解KM算法的那篇博文里，用的是找对象的例子，匹配原则是好感度尽可能大，此题目的匹配原则是回家的花费尽可能少，所以需要在博文中给出的算法模板中稍作修改，即可使用。
修改的第一个地方：
// 每个女生的初始期望值是与她相连的男生最大的好感度 for (int i = 0; i < N; ++i) { ex_girl[i] = love[i][0]; for (int j = 1; j < N; ++j) { ex_girl[i] = max(ex_girl[i], love[i][j]); } } ------改为------ // 改为取最小值 for (int i = 0; i < N; ++i) { ex_girl[i] = love[i][0]; for (int j = 1; j < N; ++j) { ex_girl[i] = min(ex_girl[i], love[i][j]); } }
修改的第二个地方：
for (int j = 0; j < N; ++j) { // 所有访问过的女生降低期望值 if (vis_girl[j]) ex_girl[j] -= d; // 所有访问过的男生增加期望值 if (vis_boy[j]) ex_boy[j] += d; // 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！ else slack[j] -= d; ------改为------ for (int j = 0; j < N; ++j) { // 改为增加 if (vis_girl[j]) ex_girl[j] += d; // 所有访问过的减少 if (vis_boy[j]) ex_boy[j] -= d; // 没有访问过的增加 else slack[j] += d;
经过以上两个地方的i修改，就成了求解最小期望和的模板，与此题目相适应，套一下模板即可。源代码戳下面链接即可，有完整注释~
源代码