HDU 1875：Prim 算法樸素實現求最小生成樹（島嶼造橋問題）

問題描述

• C ≤ 100 個島嶼，給定平面坐標。
• 僅當距離 d ∈ [10, 1000] 時可建橋，費用 = d × 100。
• 求連通所有島嶼的最小總費用，若無法連通輸出 oh!。

最小生成樹（MST）兩大算法對比

結論：本題節點少、邊稠密，Prim 樸素實現（鄰接矩陣 + 數組）最簡潔高效。

Prim 樸素算法流程

1. 任選起點（如 0）加入集合 U。
2. 維護數組 lowcost[v]：v ∉ U 到 U 的最短邊長。
3. 重複 V-1 次：
   • 在 V\U 中找 lowcost 最小的點 k 加入 U，累加權重。
   • 用 k 更新其餘點的 lowcost（鬆弛操作）。
4. 若過程中找不到可加入點（lowcost 全為 INF），圖不連通。

完整代碼（含距離約束處理）

#include 
using namespace std;
const double INF = 1e100;
struct Point { int x, y; };

double dist(const Point& a, const Point& b) {
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x) + 1.0*(a.y-b.y)*(a.y-b.y));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int C; cin >> C;
        vector p(C);
        for (int i = 0; i < C; ++i) cin >> p[i].x >> p[i].y;
        // 鄰接矩陣
        vector> d(C, vector(C, INF));
        for (int i = 0; i < C; ++i) {
            d[i][i] = 0;
            for (int j = i+1; j < C; ++j) {
                double w = dist(p[i], p[j]);
                if (w >= 10.0 && w <= 1000.0) d[i][j] = d[j][i] = w;
            }
        }
        // Prim
        vector lowcost(C, INF);
        vector inMST(C, false);
        lowcost[0] = 0;
        double sum = 0;
        int cnt = 0;
        for (int iter = 0; iter < C; ++iter) {
            int u = -1;
            double minc = INF;
            for (int i = 0; i < C; ++i)
                if (!inMST[i] && lowcost[i] < minc) { minc = lowcost[i]; u = i; }
            if (u == -1) break;  // 不連通
            inMST[u] = true;
            sum += minc;
            ++cnt;
            for (int v = 0; v < C; ++v)
                if (!inMST[v] && d[u][v] < lowcost[v])
                    lowcost[v] = d[u][v];
        }
        if (cnt == C) cout << fixed << setprecision(1) << sum * 100 << '\n';
        else cout << "oh!\n";
    }
    return 0;
}

關鍵實現細節

1. 距離約束：建圖時直接過濾 d < 10 || d > 1000 設為 INF，不加入候選邊。
2. INF 定義：用 1e100 而非 0x3f3f3f3f，避免 double 比較問題。
3. 起點選擇：任意點均可，選 0 簡單。
4. 不連通判斷：cnt != C 或某輪找不到 u（minc == INF）。
5. 輸出格式：費用 = 距離和 × 100，保留 1 位小數。

複雜度分析

• 建圖：O(C²) 計算所有對距離。
• Prim 主循環：C 輪 × O(C) 掃描 lowcost = O(C²)。
• C ≤ 100 時 10⁴ 級操作，瞬間完成。

常見錯誤避坑

• 用 int 存儲距離 → 精度丟失，需 double。
• lowcost 初始化忘記設 lowcost[0]=0，導致起點不被選中。
• 鬆弛條件寫反：if (d[u][v] < lowcost[v]) 而非 lowcost[u]。
• 輸出未乘 100 或精度格式錯誤。

總結

HDU 1875 是 Prim 樸素實現的完美練習題：小規模稠密圖、幾何權重、邊約束。掌握「鄰接矩陣 + lowcost 數組 + 掃描最小值」模板，配合幾何距離計算與約束過濾，即可輕松 AC。對於更大稀疏圖，再升級為 priority_queue 堆優化版（O(E log V)）。

1. 上一篇文章： POJ 3258 River Hopscotch：二分答案求移除石子後最短跳躍最大值
2. 下一篇文章： UVA Matrix Chain Multiplication：括號化矩陣鏈乘法代價計算

C++ 入門

UVA 1401 Remember the Word：Trie + DP 求單詞拆分方案數

問題描述 給定長度 ≤ 300,000 的目標字符串 S。

C++ 引用傳遞與指針傳遞函數參數深度解析

C++ 引用傳遞與指針傳遞函數參數深度解析 核心概念對比

Eclipse + MinGW C++ 控制台無輸出問題完整解決方案

問題現象 Eclipse CDT 使用 MinGW 編譯 C

0/1 背包問題：動態規劃遞推法完整解析與代碼模板

從貪心失敗到 DP 遞推：0/1 背包核心思想 給定容量 m