HDU 1533 Going Home KM 算法 最優二分匹配

問題

網格地圖包含 'm'（人）和 'H'（房子），每人分配一間不同房子，最小化總曼哈頓距離。人數 = 房數 ≤ 100。

模型：二分圖最小權完美匹配

• 左部：人，右部：房
• 邊權：cost = 300 - dist（轉為最大權匹配，KM 算法求最大權）
• 答案 = 人數*300 - maxWeight

KM 算法（Kuhn-Munkres）核心步驟

1. 可行頂標初始化：lx[i] = max_j w[i][j], ly[j] = 0
2. 匈牙利擴展：在相等子圖（lx[i]+ly[j]==w[i][j]）中尋找增廣路
3. 修改頂標：若找不到增廣路，計算 δ = min_{x∈S, y∉T} (lx[x]+ly[y]-w[x][y])，更新 lx[x]-=δ, ly[y]+=δ
4. 重複直到完美匹配

Slack 優化版關鍵代碼

bool dfs(int u) {
    vx[u] = true;
    for (int v = 0; v < n; ++v) {
        if (vy[v]) continue;
        int gap = lx[u] + ly[v] - w[u][v];
        if (gap == 0) {
            vy[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u; return true;
            }
        } else slack[v] = min(slack[v], gap);
    }
    return false;
}

void km() {
    fill(lx, lx+n, 0);
    fill(ly, ly+n, 0);
    fill(match, match+n, -1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            lx[i] = max(lx[i], w[i][j]);

    for (int i = 0; i < n; ++i) {
        fill(slack, slack+n, INF);
        while (true) {
            fill(vx, vx+n, false);
            fill(vy, vy+n, false);
            if (dfs(i)) break;
            int d = INF;
            for (int j = 0; j < n; ++j) if (!vy[j]) d = min(d, slack[j]);
            for (int j = 0; j < n; ++j) {
                if (vx[j]) lx[j] -= d;
                if (vy[j]) ly[j] += d;
                else slack[j] -= d;
            }
        }
    }
}

複雜度與注意點

• O(n³) ≈ 10⁶ 操作，n≤100 極快
• 需保證人數 = 房數（題目隱含）
• 曼哈頓距離：|x1-x2| + |y1-y2|
• 權值轉換常數 300 > 最大可能距離 (200)，確保正權