POJ 3723 Conscription：Kruskal 求最大權森林轉化最小生成樹

問題建模

招募 N 名女兵、M 名男兵，每人基礎成本 10000。若異性間有關係值 d（0 < d < 10000），且一方已招募，另一方成本減少 d（即 10000-d）。每人最多使用一條關係。求招募所有人最小總成本。

等價轉化：建立二分圖（女兵 0..N-1，男兵 0..M-1 → 偏移 N），邊權為 d。選擇若干邊使所有點被覆蓋（每點度 ≤1），最大化邊權和。即 **最大權匹配/森林**。

關鍵轉化：最大權森林 → 最小生成樹

總基礎成本 = (N+M) * 10000。每使用一條關係邊 (u,v,d)，總成本減少 d。最大化減少量 = 最大化所選邊權和。

因每人最多用一條關係 → 所選邊構成 **森林**（無環）。求最大權森林 = 對邊權取負，求 **最小生成樹**（Kruskal/Prim）。

Kruskal 算法實現

struct Edge {
    int u, v, d; // d 為關係值
    bool operator<(const Edge& o) const { return d > o.d; } // 降序，取大邊
};

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, M, R; scanf("%d%d%d", &N, &M, &R);
        vector edges;
        for (int i = 0; i < R; ++i) {
            int x, y, d; scanf("%d%d%d", &x, &y, &d);
            edges.push_back({x, y + N, d}); // 男兵偏移 N
        }
        sort(edges.begin(), edges.end()); // d 降序
        
        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.d;
            }
        }
        long long ans = 1LL * (N + M) * 10000 - saved;
        printf("%lld\n", ans);
    }
}

關鍵點解析