POJ 1861 Network：Kruskal 求最小生成樹中最大邊權最小化

題目核心

給定 N 個樞紐 (2≤N≤1000) 和 M 條可能連接 (1≤M≤15000)，每條連接有長度。需找出一種連接方案使所有樞紐連通，且單條纜線最大長度最小。輸出該最大長度、使用纜線數及具體連接對。

關鍵洞察

Kruskal 算法按邊權從小到大貪心選擇，構建的 MST 自然滿足「最大邊權最小」的性質。因為若存在最大邊權更小的生成樹，則其邊權序列字典序更小，違背 Kruskal 的最優性。

算法流程

1. 讀入所有邊，按權值升序排序
2. 並查集逐條嘗試加入邊，不成環則納入 MST
3. 記錄納入邊的最大權值 maxEdge 及邊列表
4. 邊數達到 N-1 即可停止

精簡代碼實現

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

const int MAXM = 15005;
int fa[MAXM], n, m;
struct Edge { int u, v, w; } e[MAXM];
int ansU[MAXM], ansV[MAXM], maxEdge = 0, edgeCnt = 0;

bool cmp(Edge a, Edge b) { return a.w < b.w; }
void UF_init() { for (int i = 1; i <= n; i++) fa[i] = i; }
int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void Union(int a, int b) { fa[Find(a)] = Find(b); }

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        sort(e, e + m, cmp);
        UF_init(); maxEdge = 0; edgeCnt = 0;
        for (int i = 0; i < m; i++) {
            if (Find(e[i].u) != Find(e[i].v)) {
                Union(e[i].u, e[i].v);
                ansU[edgeCnt] = e[i].u;
                ansV[edgeCnt] = e[i].v;
                maxEdge = max(maxEdge, e[i].w);
                if (++edgeCnt == n - 1) break;
            }
        }
        printf("%d\n%d\n", maxEdge, edgeCnt);
        for (int i = 0; i < edgeCnt; i++) printf("%d %d\n", ansU[i], ansV[i]);
    }
    return 0;
}

樣例修正說明

原題樣例輸出格式有誤，正確應為：

1
4
1 2
1 3
3 4

即最大邊長 1，使用 4 條纜線，具體連接如上。代碼輸出格式完全符合要求。

複雜度分析

• 排序：O(M log M)
• 並查集操作：近似 O(M α(N))
• 總體：O(M log M)，輕鬆通過限制