POJ 1251 Jungle Roads 最小生成樹 Kruskal 算法

題目大意

給定一個無向加權圖，部分邊已預先連接（權值視為 0），求連接所有村莊的最小總代價。標準最小生成樹（MST）問題，資料範圍較小（N ≤ 30），Kruskal 算法足以通過。

解題思路

1. 邊集構建：讀取鄰接矩陣，將所有 i < j 的邊加入列表。若兩村莊已有道路（輸入標記），將該邊權值設為 0，確保其優先被選入 MST。
2. Kruskal 算法流程：
   • 所有邊按權值升序排序
   • 初始化並查集，每個節點自成一集
   • 遍歷邊，若兩端點屬於不同集合，合併並累加權值
   • 直到選入 N-1 條邊或遍歷完畢
3. 並查集優化：路徑壓縮 + 按秩合併（本題規模小，基本版即可）。

代碼實現（C++）

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

const int MAXN = 32;
const int MAXE = 1000;

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

int parent[MAXN];
Edge edges[MAXE];
int edgeCnt;

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

bool unionSet(int a, int b) {
    int ra = findSet(a), rb = findSet(b);
    if (ra == rb) return false;
    parent[ra] = rb;
    return true;
}

int kruskal(int n) {
    sort(edges, edges + edgeCnt);
    for (int i = 1; i <= n; ++i) parent[i] = i;
    int sum = 0, cnt = 0;
    for (int i = 0; i < edgeCnt && cnt < n - 1; ++i) {
        if (unionSet(edges[i].u, edges[i].v)) {
            sum += edges[i].w;
            ++cnt;
        }
    }
    return sum;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        static int dist[MAXN][MAXN];
        static bool connected[MAXN][MAXN];
        memset(connected, 0, sizeof(connected));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &dist[i][j]);

        int m; scanf("%d", &m);
        while (m--) {
            int x, y; scanf("%d%d", &x, &y);
            connected[x][y] = connected[y][x] = true;
        }

        edgeCnt = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                edges[edgeCnt++] = {i, j, connected[i][j] ? 0 : dist[i][j]};

        printf("%d\n", kruskal(n));
    }
    return 0;
}

複雜度與注意點

• 時間複雜度：O(E log E) ≈ O(N² log N)，N ≤ 30 時極快
• 預連接邊權值設 0 是關鍵技巧，保證其必被選入
• 輸入包含多測試案例，以 N=0 結束