POJ 3723 徵兵：最大生成樹變形解決雙邊匹配問題

題目大意

有 n 個男性和 m 個女性，共 n+m 人。每人有基礎成本 10000。r 條潛在配對，每條配對 (x, y, w) 表示男性 x 和女性 y 配對可節省 w 成本。每人最多屬於一對。求最小總成本。

模型轉化：最大生成樹 / 最大權匹配

初始總成本 = (n + m) * 10000。
選擇配對即從圖中選邊，每條邊權重為節省成本 w。
約束：每個頂點度 ≤ 1 (匹配)。
目標：最大化所選邊權重和 → 最大權匹配。
但本題圖為二分圖 (男性集合、女性集合)，且無奇環約束，可用克魯斯克爾算法求最大生成森林等價求解！

為什麼克魯斯克爾有效？

• 克魯斯克爾構建最大生成樹/森林：按權重降序加邊，不形成環
• 二分圖中任何環長度為偶數，但匹配要求度 ≤ 1，即森林中每個連通分量為單條邊或孤立點
• 克魯斯克爾加邊條件「不形成環」在二分圖匹配中等價於「兩端點未被匹配」
• 因為若兩端點已在同一連通分量，在匹配森林中意味著它們已通過其他邊間接連接，加上這條邊會形成長度 ≥ 4 的環，違反度 ≤ 1

因此：按 w 降序，若兩端點所在並查集不同，則合並並累加 w 即得最大權匹配！

完整代碼

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const { return w > other.w; } // 降序
};

const int MAXN = 20005; // n,m ≤ 10000
int fa[MAXN];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m, r;
        cin >> n >> m >> r;
        vector<Edge> edges;
        edges.reserve(r);
        for (int i = 0; i < r; ++i) {
            int x, y, w;
            cin >> x >> y >> w;
            edges.push_back({x, y + n, w}); // 女性編號偏移 n
        }
        sort(edges.begin(), edges.end()); // 按 w 降序

        // 初始化並查集
        for (int i = 0; i < n + m; ++i) fa[i] = i;

        long long saved = 0;
        for (auto& e : edges) {
            int fu = find(e.u), fv = find(e.v);
            if (fu != fv) {
                fa[fu] = fv;
                saved += e.w;
            }
        }

        long long total = 1LL * (n + m) * 10000 - saved;
        cout << total << '\n';
    }
    return 0;
}

關鍵點總結

複雜度分析

• 排序：O(r log r)，r ≤ 100000
• 並查集操作：O(r α(n+m))，近似線性
• 總體：O(r log r)，極快

延伸思考

• 若圖非二分圖，克魯斯克爾求最大生成樹不等價於最大權匹配 (後者為一般圖匹配，需 Blossom 算法)
• 本題利用二分圖特殊結構，將 O(n³) 匹配問題降維為 O(r log r) 排序+並查集
• 類似思想：最小生成樹構建、聚類 (Kruskal 停止條件變為連通分量數 = k)

本題是「並查集 + 貪心」解決匹配問題的教科書級範例，展示了圖論中二分圖匹配與生成樹的深刻聯繫。