HDU 1863 暢通工程 最小生成樹解法

問題描述

給定 M 個村莊（節點）和 N 條可能建設的道路（邊），每條道路有建設成本。要求選擇若干條道路使所有村莊連通，且總成本最小。若無法連通所有村莊，輸出 "?"。

解題思路

這是標準的最小生成樹（MST）問題。村莊數 M < 100，邊數 N 可達數千，適合使用 Kruskal 算法或 Prim 算法。

Kruskal 算法步驟

1. 將所有邊按權重從小到大排序
2. 初始化並查集，每個村莊自成一個集合
3. 遍歷排序後的邊，若邊的兩端點屬於不同集合，則合併並累加成本
4. 當選取的邊數達到 M - 1 條，或遍歷完所有邊時停止
5. 最後檢查並查集中是否只有一個根節點，判斷是否連通

並查集優化

int parent[MAXM];
int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) parent[x] = y;
}

完整代碼框架

struct Edge { int u, v, w; } edges[MAXN];
bool cmp(Edge a, Edge b) { return a.w < b.w; }

int main() {
    while (scanf("%d%d", &N, &M), N) {
        for (int i = 0; i < N; ++i)
            scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
        
        sort(edges, edges + N, cmp);
        for (int i = 1; i <= M; ++i) parent[i] = i;
        
        int ans = 0, cnt = 0;
        for (int i = 0; i < N && cnt < M - 1; ++i) {
            if (find(edges[i].u) != find(edges[i].v)) {
                unite(edges[i].u, edges[i].v);
                ans += edges[i].w;
                ++cnt;
            }
        }
        
        if (cnt == M - 1) printf("%d\n", ans);
        else puts("?");
    }
    return 0;
}

關鍵點總結

• 邊權為正整數，無負權環問題
• 並查集路徑壓縮保證近似 O(1) 操作
• 輸入以 N=0 結束，注意不輸出該用例結果
• 若圖不連通（最終邊數 < M-1），輸出 "?"