POJ 1751 Highways 最小生成樹：Prim 演算法與預連邊處理

題目大意

給定 n (≤ 750) 個點的平面座標，部分點對已有公路相連（權重視為 0）。求仍需建設的公路集合，使所有點連通且總長度最小（輸出需新建邊的端點）。

演算法選型：Prim vs Kruskal

• Kruskal：邊排序 O(E log E)，E = n(n-1)/2 ≈ 280k，排序常數較大；需額外儲存所有邊。
• Prim (鄰接矩陣 + 陣列優先隊列)：O(n²)，n=750 → 562k 運算，無需額外邊表，極適合稠密圖；且易於記錄前驅節點輸出樹邊。

本題採用 Prim + 前驅陣列 實作。

核心資料結構

int n;                      // 點數
int x[MAXN], y[MAXN];       // 座標
int dist[MAXN][MAXN];       // 鄰接矩陣（平方距離，避免 sqrt）
int minDist[MAXN];          // 非樹頂點到樹的最短距離
int parent[MAXN];           // 前驅節點，用於輸出樹邊
bool inMST[MAXN];           // 是否已加入生成樹

關鍵步驟

1. 讀入座標，計算兩點間平方距離 (dx*dx + dy*dy) 填入 dist（對稱）。
2. 處理預連邊：讀入 q 條既有公路，將對應 dist[u][v] = dist[v][u] = 0。
3. Prim 主循環：
   • 初始化：minDist[1]=0，其餘 INF；parent[i]=1。
   • 重複 n 次：在未入樹頂點中找 minDist 最小者 u，加入樹。
   • 若 minDist[u] > 0（非預連邊），輸出 parent[u] u。
   • 鬆弛：對每個未入樹頂點 v，若 dist[u][v] < minDist[v] 更新 minDist[v] 與 parent[v]。

完整程式碼 (C99)

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define MAXN 755
#define INF  0x3f3f3f3f

int n;
int x[MAXN], y[MAXN];
int dist[MAXN][MAXN];
int minDist[MAXN], parent[MAXN];
bool inMST[MAXN];

int main(void) {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i) scanf("%d %d", &x[i], &y[i]);

        /* 建立鄰接矩陣：平方距離 */
        for (int i = 1; i <= n; ++i) {
            dist[i][i] = 0;
            for (int j = 1; j < i; ++j) {
                int dx = x[i] - x[j];
                int dy = y[i] - y[j];
                dist[i][j] = dist[j][i] = dx*dx + dy*dy;
            }
        }

        int q; scanf("%d", &q);
        while (q--) {
            int u, v; scanf("%d %d", &u, &v);
            dist[u][v] = dist[v][u] = 0;   /* 預連邊權重 0 */
        }

        /* Prim */
        memset(inMST, 0, sizeof(inMST));
        for (int i = 1; i <= n; ++i) {
            minDist[i] = INF;
            parent[i] = 1;
        }
        minDist[1] = 0;

        for (int iter = 1; iter <= n; ++iter) {
            int u = -1, best = INF;
            for (int i = 1; i <= n; ++i)
                if (!inMST[i] && minDist[i] < best) {
                    best = minDist[i];
                    u = i;
                }
            if (u == -1) break;          // 圖不連通（題目保證連通）
            inMST[u] = true;
            if (minDist[u] > 0)          // 非預連邊才輸出
                printf("%d %d\n", parent[u], u);

            for (int v = 1; v <= n; ++v)
                if (!inMST[v] && dist[u][v] < minDist[v]) {
                    minDist[v] = dist[u][v];
                    parent[v] = u;
                }
        }
    }
    return 0;
}

複雜度分析

• 時間：O(n²) ≈ 56 萬次迴圈，極易在 1 秒內通過。
• 空間：dist[755][755] ≈ 2.3 MB，符合 64 MB 限制。

常見坑點與優化

1. 距離溢位：座標範圍未給，平方和可能超過 int，建議用 long long 或 double 存儲距離。
2. 輸出順序：Prim 依加入樹順序輸出，題目未要求特定順序，任意合法樹皆可。
3. 多測資：題目隱含多組測資（EOF 結束），外層 while(scanf(...)) 處理。
4. 優化：若 n 較大（>2000），可改用二元堆 O(E log V) 或 Fibonacci 堆 O(E + V log V)。

稠密圖 MST 首選 Prim + 鄰接矩陣，預連邊權重置 0 即可無縫融合。記錄 parent 陣列輕鬆輸出樹邊，是競程與工程中通用的技巧。