POJ 1751 Highways 解題：Prim 演算法求最小生成樹新增公路

題目大意

給定 N 個城鎮座標與 M 條已建公路。需新建公路使所有城鎮連通，且新建公路總長度最小。輸出需新建的公路邊 (兩端城鎮編號)。

解法：Prim 演算法變體

此題本質是求最小生成樹 (MST)。已建公路視為權重為 0 的邊。使用 Prim 演算法從任意點 (如 1) 開始擴展：

1. 初始化 dis[i] 為點 1 到各點的距離平方 (或已建公路為 0)。
2. 每輪選擇未加入樹中、dis 最小的點 u 加入。
3. 若加入的邊權重 > 0 (即非已建公路)，輸出該邊 (pre[u], u)。
4. 更新未加入點的 dis：dis[v] = min(dis[v], dist(u,v))。

關鍵實作細節

• 距離用平方避免開根號，不影響大小比較。
• 已建公路在鄰接矩陣中設為 0。
• N ≤ 750，鄰接矩陣 O(N^2) Prim 適用 (約 56 萬次操作)。
• 單測資測試案例，無需多案例循環。

參考程式碼核心

int dist2(int i, int j) {
    return (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
}

void prim() {
    // 初始化 dis, pre
    for (int i = 1; i <= n; ++i) {
        dis[i] = g[1][i];
        pre[i] = 1;
    }
    mark[1] = true;
    for (int iter = 1; iter < n; ++iter) {
        int u = -1, minD = INF;
        for (int i = 1; i <= n; ++i)
            if (!mark[i] && dis[i] < minD) { minD = dis[i]; u = i; }
        if (minD != 0) printf("%d %d\n", pre[u], u); // 輸出新建公路
        mark[u] = true;
        for (int v = 1; v <= n; ++v)
            if (!mark[v] && dis[v] > g[u][v]) {
                dis[v] = g[u][v];
                pre[v] = u;
            }
    }
}