HDU 1533 Going Home：最小費用最大流解決人房匹配問題

問題建模

網格地圖上有 n 個人（'m'）和 n 個房子（'H'）。每人走一步花費 1，上下左右移動。每房只能住一人。求所有人進房的最小總步數。
本質是**二分圖最小權完美匹配**，可用最小費用最大流解決。

流網絡構建

• 源點 S，匯點 T。
• 每個人節點 M_i，每個房子節點 H_j。
• 邊 S → M_i：容量 1，費用 0。
• 邊 M_i → H_j：容量 1，費用 = 曼哈頓距離 |x_i-x_j| + |y_i-y_j|。
• 邊 H_j → T：容量 1，費用 0。

SPFA 求最小費用增廣路

由於邊費用非負，也可用 Dijkstra + 潛能函數優化。但 n ≤ 100，SPFA 完全足夠。
核心流程：
1. SPFA 找 S→T 最短路（按費用）。
2. 沿路徑增廣流量 1，累加費用。
3. 重複 n 次直到滿流。

關鍵代碼結構

struct Edge { int to, cap, cost, rev; };
vector G[MAXV];
void addEdge(int u, int v, int cap, int cost) {
    G[u].push_back({v, cap, cost, (int)G[v].size()});
    G[v].push_back({u, 0, -cost, (int)G[u].size()-1});
}

pair minCostMaxFlow(int s, int t, int maxf) {
    int flow = 0, cost = 0;
    while (flow < maxf) {
        // SPFA 找最短路
        // 增廣
    }
    return {flow, cost};
}

曼哈頓距離計算優化

直接雙循環 O(n^2) 計算所有 M_i → H_j 距離，n ≤ 100 只有 1e4 對，極快。無需 BFS。

複雜度

SPFA 平均 O(E)，增廣 n 次，總 O(n * E) ≈ 100 * 1e4 = 1e6，瞬間通過。