HDU 1533 Going Home：KM 算法解二分圖最小權完美匹配

HDU 1533 Going Home：KM 算法解二分圖最小權完美匹配

題目大意

N×M 網格，n 個人 'm'、n 個房子 'H'。人走一步花 $1（曼哈頓距離）。每房住一人。求最小總花費。n,m ≤100，房子數 ≤100。

建模

• 二分圖：左側人，右側房，邊權 = -距離（取反轉最小為最大）
• KM 算法求最大權完美匹配，答案取負

KM 算法核心步驟

1. 初始頂標：lx[i] = max_j w[i][j], ly[j] = 0
2. 嘗試為每個左節點找增廣路（DFS 只走緊邊 lx+ly==w）
3. 失敗則調整頂標：d = min{ lx[u]+ly[v]-w[u][v] | u∈S, v∉T }，S 內 lx-=d，T 內 ly+=d
4. 重複直到完美匹配

關鍵代碼片段

bool dfs(int u) {
    visx[u] = true;
    for (int v = 0; v < ny; ++v) if (!visy[v]) {
        int gap = lx[u] + ly[v] - g[u][v];
        if (gap == 0) {
            visy[v] = true;
            if (link[v] == -1 || dfs(link[v])) { link[v] = u; return true; }
        } else slack[v] = min(slack[v], gap);
    }
    return false;
}

int km() {
    fill(link, link+ny, -1); fill(ly, ly+ny, 0);
    for (int i = 0; i < nx; ++i) {
        lx[i] = -INF;
        for (int j = 0; j < ny; ++j) lx[i] = max(lx[i], g[i][j]);
    }
    for (int u = 0; u < nx; ++u) {
        fill(slack, slack+ny, INF);
        while (true) {
            fill(visx, visx+nx, false); fill(visy, visy+ny, false);
            if (dfs(u)) break;
            int d = INF;
            for (int v = 0; v < ny; ++v) if (!visy[v]) d = min(d, slack[v]);
            for (int i = 0; i < nx; ++i) if (visx[i]) lx[i] -= d;
            for (int v = 0; v < ny; ++v) {
                if (visy[v]) ly[v] += d; else slack[v] -= d;
            }
        }
    }
    int ans = 0;
    for (int v = 0; v < ny; ++v) if (link[v] != -1) ans += g[link[v]][v];
    return -ans; // 取反得最小花費
}

完整流程

1. 掃描地圖記錄人/房坐標
2. 構建鄰接矩陣 g[i][j] = -|mx-hx| - |my-hy|
3. 調用 KM 獲取最小總距離

複雜度

• O(n³)，n≤100 完全足夠
• 稀疏圖可用最小費用最大流，但 KM 代碼更短

樣例

輸入：
2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0

輸出：
2
10
28

此題是 KM 算法「最小權完美匹配」的經典應用，權值取反技巧通用。