HDU 1162 Eddy's Picture：二維平面點集最小生成樹 (Prim 算法)

問題描述

給定 n (≤ 100) 個二維平面點座標。任意兩點間可建立邊，權重為**歐氏距離**。求連通所有點的**最小總邊長** (MST 權重和)，保留兩位小數。多測試用例，EOF 結束。

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

• 完全圖，n ≤ 100，O(n²) Prim 最優。
• 邊權動態計算：dist(i,j) = sqrt((xi-xj)² + (yi-yj)²)，無需預存所有邊，Prim 過程中現算現用或預計算矩陣。

完整代碼 (C)

#include 
#include 
#include 
#include 
#include 

#define MAXN 101
#define INF 1e100

typedef struct { double x, y; } Point;
Point p[MAXN];
double dist[MAXN][MAXN];
double minDist[MAXN];
int visited[MAXN];
int n;

double calcDist(int i, int j) {
    double dx = p[i].x - p[j].x;
    double dy = p[i].y - p[j].y;
    return sqrt(dx*dx + dy*dy);
}

void buildMatrix() {
    for (int i = 0; i < n; ++i) {
        dist[i][i] = INF;
        for (int j = i+1; j < n; ++j) {
            double d = calcDist(i, j);
            dist[i][j] = dist[j][i] = d;
        }
    }
}

double prim() {
    for (int i = 0; i < n; ++i) {
        minDist[i] = INF;
        visited[i] = 0;
    }
    minDist[0] = 0;
    double 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] && dist[u][v] < minDist[v])
                minDist[v] = dist[u][v];
    }
    return sum;
}

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++i)
            scanf("%lf %lf", &p[i].x, &p[i].y);
        buildMatrix();
        printf("%.2lf\n", prim());
    }
    return 0;
}

精度與性能優化

複雜度

• 時間：O(n²) = 10⁴ 距離計算 + 10⁴ Prim 循環，極快。
• 空間：O(n²) 距離矩陣 (100×100×8B = 80KB)。

Kruskal 替代方案

生成所有 n(n-1)/2 ≈ 4950 條邊，排序 O(E log E)，並查集合並。代碼量稍大，但對稀疏圖優勢明顯。本題完全圖 Prim 更簡潔。