「Going Home」回家

形式化题目

给一个 $N \times M$ 的网格，其中有 $n$ 个小人（m）和 $n$ 间房子（H），其余格子是空地（.）。小人每单位时间可以上、下、左、右移动一格，每走一步花费 1 美金，直到进入某间房子为止；每间房子只能容纳一个小人。求让所有小人都进屋的最少总花费。

网格中没有障碍物，小人也可以踩在房门格上再选择进入，所以一个小人从 $(r_1, c_1)$ 走到 $(r_2, c_2)$ 的最少步数就是曼哈顿距离 $|r_1 - r_2| + |c_1 - c_2|$ 。于是问题等价于：左侧 $n$ 个小人、右侧 $n$ 间房子的完全二分图，边权为两点间曼哈顿距离，求一个最小权完美匹配的总权值。

以样例 2 为例，3 个小人 $P_1(0,4), P_2(4,0), P_3(4,1)$ 与 3 间房子 $H_1(0,0), H_2(0,1), H_3(4,4)$ 的权值矩阵（单位：步）：

小人 \ 房子	$H_1(0,0)$	$H_2(0,1)$	$H_3(4,4)$
$P_1(0,4)$	4	3	4
$P_2(4,0)$	4	5	4
$P_3(4,1)$	5	4	3

表格每格是对应小人走到对应房子的最少步数。从表中挑 $n$ 个不同行、不同列的格子使和最小：取 $P_1 \to H_2$ （3）、 $P_2 \to H_1$ （4）、 $P_3 \to H_3$ （3），总和 $3 + 4 + 3 = 10$ ，正是样例输出。

正解

思路

朴素做法是枚举小人与房子的全部对应方式：把 $n$ 间房子的一个全排列依次分给 $n$ 个小人，总花费为 $\sum_i \mathrm{cost}(i, \pi(i))$ ，在 $n!$ 个排列里取最小。 $n$ 最大为 100 时 $100!$ 完全不可接受，瓶颈在于「逐个决定谁配谁」的指数级枚举。

观察每次配对的代价只由「哪个小人、哪间房子」决定，与其他人如何配对无关——这正是二分图最小权完美匹配的结构：左部 $n$ 个小人、右部 $n$ 间房子，边 $(i, j)$ 的权为曼哈顿距离，要找 $n$ 条两两不共享端点的边使权值和最小。求它用匈牙利算法（KM）：

为每个小人 $i$ 和房子 $j$ 维护顶标 $pot\_l[i], pot\_r[j]$ ，始终保持可行性

pot\_l[i] + pot\_r[j] \leqslant cost(i, j)

取等号的边构成「相等子图」。把所有顶标加起来： $\sum_i pot\_l[i] + \sum_j pot\_r[j}$ 是任何完美匹配总权值的下界，而只要相等子图里存在完美匹配，它的每条边都顶着等式取到下界，总权恰好触到这个下界，因而全局最优。

算法逐轮把小人挂入交错树：从当前小人 $i$ 出发，只沿相等边在交错树上扩展——树上的房子沿匹配边回退到小人，小人再用相等边连到树外房子。若碰到空房，就找到了一条增广路，翻转匹配、进入下一轮。若树外没有空房可达，则对树上点整体改顶标：左部点 $+ \delta$ 、右部点 $-\delta$ ，其中 $\delta$ 是「树上小人连到树外房子」的最小松弛量 $cost - pot\_l - pot\_r$ 。这样一加一减，树内相等边原样保留，树外房子的松弛量同步减 $\delta$ ，至少一条边松弛归零进入相等子图让交错树继续生长，而所有边的可行性都保持不破。 $n$ 轮后得到完美匹配。

用上文样例 2 的权值矩阵示意匹配过程（边上的数字为权值，加粗为最终匹配）：

graph LR
    subgraph L["左部：小人"]
        P1["P1"]
        P2["P2"]
        P3["P3"]
    end
    subgraph R["右部：房子"]
        H1["H1"]
        H2["H2"]
        H3["H3"]
    end
    P1 ---|"4"| H1
    P1 ==>|"3"| H2
    P1 ---|"4"| H3
    P2 ==>|"4"| H1
    P2 ---|"5"| H2
    P2 ---|"4"| H3
    P3 ---|"5"| H1
    P3 ---|"4"| H2
    P3 ==>|"3"| H3

KM 每轮在交错树上做 $O(n)$ 的松弛扫描，共 $n$ 轮、每轮最多扩展 $n$ 个房子，总复杂度 $O(n^3)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll FAR = 1000000000000000000LL;

int cost[105][105];   // 小人 -> 房子的曼哈顿距离

ll pot_l[105];        // 左部顶标
ll pot_r[105];        // 右部顶标
int match_r[105];     // match_r[j] = 配到房子 j 的小人，0 表示空房
int prev_[105];       // 交错树上房子 j 的前驱房子
ll slack[105];
bool used[105];

// 匈牙利（KM）求 n×n 最小权完美匹配
ll min_cost_perfect_matching(int n) {
    for (int i = 0; i <= n; i++) { pot_l[i] = 0; pot_r[i] = 0; }
    for (int i = 0; i <= n; i++) match_r[i] = 0;

    for (int i = 1; i <= n; i++) {
        match_r[0] = i;
        for (int j = 0; j <= n; j++) slack[j] = FAR;
        for (int j = 0; j <= n; j++) used[j] = false;
        int j0 = 0;
        while (true) {
            used[j0] = true;
            int u = match_r[j0];
            ll delta = FAR;
            int j1 = 0;
            for (int j = 1; j <= n; j++) {
                if (!used[j]) {
                    ll gap = (ll)cost[u - 1][j - 1] - pot_l[u] - pot_r[j];
                    if (gap < slack[j]) {
                        slack[j] = gap;
                        prev_[j] = j0;
                    }
                    if (slack[j] < delta) {
                        delta = slack[j];
                        j1 = j;
                    }
                }
            }
            for (int j = 0; j <= n; j++) {
                if (used[j]) {
                    pot_l[match_r[j]] += delta;
                    pot_r[j] -= delta;
                } else {
                    slack[j] -= delta;
                }
            }
            j0 = j1;
            if (match_r[j0] == 0) break;
        }
        while (j0) {
            match_r[j0] = match_r[prev_[j0]];
            j0 = prev_[j0];
        }
    }

    ll total = 0;
    for (int j = 1; j <= n; j++)
        total += (ll)cost[match_r[j] - 1][j - 1];
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (true) {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        vector<string> grid(n);
        for (int i = 0; i < n; i++) cin >> grid[i];

        vector<pair<int, int> > people, houses;
        for (int r = 0; r < n; r++)
            for (int c = 0; c < m; c++) {
                if (grid[r][c] == 'm') people.push_back(make_pair(r, c));
                else if (grid[r][c] == 'H') houses.push_back(make_pair(r, c));
            }
        int cnt = (int)people.size();
        for (int i = 0; i < cnt; i++)
            for (int j = 0; j < cnt; j++)
                cost[i][j] = abs(people[i].first - houses[j].first)
                           + abs(people[i].second - houses[j].second);
        cout << min_cost_perfect_matching(cnt) << "\n";
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 02:47
# update_at: 2026-10-02 03:30

import sys

FAR = 10 ** 18  # 松弛量初值：比任何曼哈顿距离都大，表示「还没连到交错树上」


def min_cost_perfect_matching(cost: list[list[int]]) -> int:
    """匈牙利算法（KM）：求 n×n 最小权完美匹配，返回最小总权值。

    顶标维持可行性 pot_l[i] + pot_r[j] <= cost[i][j]，取等号的边构成「相等子图」。
    只要相等子图里有完美匹配，每条匹配边都顶着等式取到下界，和必为全局最小。
    每轮把一个人 i 挂入交错树找增广路；找不到时给树上点整体改顶标：
    左部点 +delta、右部点 -delta（delta 是树到树外房子的最小松弛量），
    相等边一加一减保持不动，树外松弛量同步减 delta，至少冒出一条新等式边且可行性不破。
    """
    n = len(cost)
    pot_l = [0] * (n + 1)   # 左部（小人）顶标
    pot_r = [0] * (n + 1)   # 右部（房子）顶标
    match_r = [0] * (n + 1)  # match_r[j] = 配到房子 j 的小人，0 表示空房
    prev = [0] * (n + 1)     # 交错树上房子 j 的前驱房子

    for i in range(1, n + 1):
        match_r[0] = i        # 虚拟房子 0 指向本轮待增广的小人 i，当树根
        slack = [FAR] * (n + 1)   # 树外房子 j 到树上小人的最小松弛量
        used = [False] * (n + 1)
        j0 = 0
        while True:
            used[j0] = True
            row = cost[match_r[j0] - 1]   # 沿匹配边回退到的树上小人
            delta, j1 = FAR, 0
            for j in range(1, n + 1):      # 用新入树的小人刷新松弛量
                if not used[j]:
                    gap = row[j - 1] - pot_l[match_r[j0]] - pot_r[j]
                    if gap < slack[j]:
                        slack[j], prev[j] = gap, j0
                    if slack[j] < delta:
                        delta, j1 = slack[j], j
            for j in range(n + 1):         # 树上左 +delta 右 -delta，树外松弛量减 delta
                if used[j]:
                    pot_l[match_r[j]] += delta
                    pot_r[j] -= delta
                else:
                    slack[j] -= delta
            j0 = j1
            if match_r[j0] == 0:           # 撞上空房 = 找到增广路
                break
        while j0:                          # 沿 prev 翻转整条增广路
            match_r[j0] = match_r[prev[j0]]
            j0 = prev[j0]

    return sum(cost[match_r[j] - 1][j - 1] for j in range(1, n + 1))


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    while True:
        n, m = int(next(data)), int(next(data))
        if n == 0 and m == 0:                    # 题面约定的结束标记
            break
        grid = [next(data) for _ in range(n)]
        people = [(r, c) for r in range(n) for c in range(m) if grid[r][c] == ord('m')]
        houses = [(r, c) for r in range(n) for c in range(m) if grid[r][c] == ord('H')]
        # 权值取曼哈顿距离：空地、房门格都能踩，最短步数就是 |dr| + |dc|
        cost = [[abs(pr - hr) + abs(pc - hc) for hr, hc in houses] for pr, pc in people]
        out.append(str(min_cost_perfect_matching(cost)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度 $O(n^3)$ ：外层枚举 $n$ 个小人，内层交错树每扩展一个房子扫描一遍 $n$ 个树外房子。 $n \leqslant 100$ 时约 $10^6$ 次基本操作。空间复杂度 $O(n^2)$ ，用于存权值矩阵（ $100 \times 100$ ，可忽略）。

总结

把「最少步数」算成曼哈顿距离后，题目就是标准的二分图最小权完美匹配：朴素的全排列枚举是 $O(n!)$ ，瓶颈在于指数级的配对枚举；KM 用顶标维持下界、用相等子图上的增广路逐轮确定匹配边，把复杂度降到 $O(n^3)$ 。读入时注意多组数据以 0 0 结束，权值矩阵由小人、房子坐标列表用推导式一次算出。

「Going Home」 回家

目录

形式化题目

正解

思路

代码

复杂度

总结