問題背景

有 n 男 m 女，每個人有戰力值。選擇若干男女配對，每人最多屬於一對，目標最大化配對雙方戰力之和。等價於在二分圖中求最大權匹配，但本題特殊：可構造完整圖，邊權為雙方戰力和，求最大生成樹（或森林）後再匹配。實際常見解法：將所有人作為節點，男女之間連邊權為戰力和，同性之間連邊權 0，求最大生成樹，答案 = 總戰力和 × 2 - MST 權重和。（具體建模視具體題面，此處略）

最大生成樹 vs 最小生成樹

Kruskal 算法：將邊按權重降序排序，依次加入不形成環的邊。僅排序順序與最小生成樹相反，其餘並查集判環、邊數達到 n-1 停止完全一致。

代碼實現

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct Edge { int u, v, w; } e[60000];
int fa[40010], ecnt;

bool cmp(Edge a, Edge b) { return a.w > b.w; } // 降序

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

int kruskal(int n) {
    sort(e, e+ecnt, cmp);
    for (int i=1; i<=n; ++i) fa[i]=i;
    int ans=0, cnt=0;
    for (int i=0; i>T;
    while (T--) {
        int n,m,R; cin>>n>>m>>R;
        ecnt=0;
        // 讀取戰力值並構造邊...
        // 略：具體建模代碼
        cout << kruskal(n+m) << '\n';
    }
    return 0;
}

關鍵點

1. 邊權類型：戰力和可達 20000，int 足夠；總權重和用 long long。
2. 並查集路徑壓縮：fa[x]=find(fa[x]) 保證近乎 O(1)。
3. 邊數上限：完全圖邊數 O((n+m)²)，但題目通常給出具體邊列表，直接讀入。
4. 多測試用例：每案例重置 ecnt、fa、邊數組。

常見變體

• 最小生成樹：cmp 改為 a.w < b.w。
• 次小生成樹：枚舉 MST 邊，強制排除/包含重跑。
• 帶限制條件的生成樹：如度數限制，需更複雜算法（Kirchhoff 矩阵樹定理或 DP）。

總結

POJ 3723 是最大生成樹的標準模板題。核心在於正確建模將問題轉化為 MST，然後 Kruskal + 並查集 模板套用。注意邊權降序、並查集初始化、長整型防溢出三個細節，即可穩健 AC。