HDU 1233 還是暢通工程：完全圖上的 Prim 算法求 MST

問題描述

給定 n (≤ 100) 個點的**完全圖**，輸入所有 n(n-1)/2 條邊的長度。求連通所有點的**最小道路總長度** (MST 權重和)。多測試用例，n=0 結束。

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

• 完全圖邊數 E = V²，鄰接矩陣 O(V²) 空間最優，Prim O(V²) 時間最優 (堆優化反而慢)。
• 同 HDU 1301，模板通用。

完整代碼 (C)

#include 
#include 
#include 

#define MAXN 101
#define INF 100000000

int n;
int graph[MAXN][MAXN];
int minDist[MAXN];
int visited[MAXN];

int prim() {
    for (int i = 0; i < n; ++i) {
        minDist[i] = INF;
        visited[i] = 0;
    }
    minDist[0] = 0;
    int sum = 0;

    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int j = 0; j < n; ++j)
            if (!visited[j] && (u == -1 || minDist[j] < minDist[u]))
                u = j;

        visited[u] = 1;
        sum += minDist[u];

        for (int v = 0; v < n; ++v)
            if (!visited[v] && graph[u][v] < minDist[v])
                minDist[v] = graph[u][v];
    }
    return sum;
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        // 初始化
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                graph[i][j] = (i == j) ? 0 : INF;

        int m = n * (n - 1) / 2;
        for (int i = 0; i < m; ++i) {
            int x, y, d;
            scanf("%d %d %d", &x, &y, &d);
            --x; --y; // 1-based -> 0-based
            graph[x][y] = graph[y][x] = d;
        }

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

關鍵點總結

複雜度

• 時間：O(n²) = 10⁴ 操作/用例，瞬間通過。
• 空間：101×101 int ≈ 40KB。