HDU 1301 Jungle Roads 最小生成樹：Prim 算法鄰接矩陣實現

問題描述

給定 n (≤ 26) 個村莊 (用大寫字母 A-I 表示)，輸入 n-1 行，第 i 行給出村莊 i 到其他村莊的道路長度。求連通所有村莊的**最小道路總長度** (最小生成樹 MST 權重和)。多測試用例，n=0 結束。

算法選型：Prim 算法 (鄰接矩陣版)

• 稠密圖 (n ≤ 26)，鄰接矩陣 O(n²) 空間時間極優。
• Prim 核心：維護「已在樹中頂點集」到「未在樹中頂點」的**最短跨集邊**，貪心選擇最小邊加入。
• 優化：用 minDist[v] 記錄頂點 v 到當前樹的最短距離，每次加入新頂點後更新鄰居的 minDist。

關鍵代碼 (C++ 完整可編譯)

#include 
#include 
#include 
#include 

const int MAXN = 27;
const int INF = 0x3f3f3f3f;

int n;
int graph[MAXN][MAXN];
int minDist[MAXN];
bool inMST[MAXN];

void resetGraph(int n) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            graph[i][j] = (i == j) ? 0 : INF;
}

int prim(int n) {
    std::fill(minDist, minDist + n, INF);
    std::fill(inMST, inMST + n, false);
    minDist[0] = 0; // 從頂點 0 開始
    int sum = 0;

    for (int i = 0; i < n; ++i) {
        // 1. 找未在樹中且 minDist 最小的頂點 u
        int u = -1;
        for (int j = 0; j < n; ++j)
            if (!inMST[j] && (u == -1 || minDist[j] < minDist[u]))
                u = j;

        if (minDist[u] == INF) return -1; // 圖不連通 (本題保證連通)
        inMST[u] = true;
        sum += minDist[u];

        // 2. 更新鄰居距離
        for (int v = 0; v < n; ++v)
            if (!inMST[v] && graph[u][v] < minDist[v])
                minDist[v] = graph[u][v];
    }
    return sum;
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        resetGraph(n);
        // 輸入 n-1 行
        for (int i = 0; i < n - 1; ++i) {
            char from; int m;
            scanf(" %c %d", &from, &m); // 格式: A 3 ...
            int u = from - 'A';
            for (int k = 0; k < m; ++k) {
                char to; int w;
                scanf(" %c %d", &to, &w);
                int v = to - 'A';
                graph[u][v] = graph[v][u] = std::min(graph[u][v], w); // 可能有重邊取小
            }
        }
        printf("%d\n", prim(n));
    }
    return 0;
}

輸入解析細節

• 輸入格式：A 3 B 5 C 10 D 20 表示 A 連 B(5), C(10), D(20)。
• 字符轉索引：ch - 'A'。
• 無向圖：graph[u][v] = graph[v][u]。
• 重邊處理：取最小權重。

複雜度分析

• 時間：O(n²) = 26² ≈ 676 操作/測試用例，極快。
• 空間：O(n²) 矩陣 + O(n) 輔助數組。

常見錯誤避坑

1. scanf 讀字符時跳過空白：" %c" (前導空格)。
2. 初始化 minDist 為 INF，minDist[0]=0。
3. 判斷 u == -1 或 minDist[u] == INF 處理不連通情況 (本題無需但良好習慣)。
4. 結果用 int 足夠 (邊權 < 100, n < 26, 總和 < 2600)。