HDU Constructing Roads：Kruskal 算法構建最小生成樹

問題描述

有 N 個村莊（1~N），已知任意兩村莊間的距離（N×N 矩陣），另有 Q 條已建道路。需新建道路使所有村莊連通，且新建道路總長度最小。輸出最小總長度。

解題思路：最小生成樹（Kruskal）

1. 將所有可能的邊（i,j）及其距離存入邊列表（只取上三角或下三角避免重複）。
2. 初始化並查集，將已建的 Q 條道路先合併（union）。
3. 對所有邊按權值升序排序，依次嘗試加入：若兩端點不在同一集合，則合併並累加權值。
4. 最終累加和即為答案。

時間複雜度 O(N² log N)，N ≤ 100 完全足夠。

參考代碼 (C++)

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

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const { return w < other.w; }
} edges[10000];

int parent[105];

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

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        int m = 0;
        for (int i = 1; i <= n; ++i) parent[i] = i;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                int d; scanf("%d", &d);
                if (i < j) { edges[m++] = {i, j, d}; }
            }
        }
        int q; scanf("%d", &q);
        for (int i = 0; i < q; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            parent[find(a)] = find(b);
        }
        sort(edges, edges + m);
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            int u = find(edges[i].u), v = find(edges[i].v);
            if (u != v) {
                parent[u] = v;
                ans += edges[i].w;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

範例

輸入：
3
0 990 692
990 0 179
692 179 0
1
1 2

輸出：
179

解析：村莊 1-2 已連通，只需加邊 2-3（權值 179）即可全圖連通。