HDU 1233 還是暢通工程：最小生成樹 Prim 與 Kruskal 實現

問題描述

給定 n（≤ 100）個點的完全圖，每條邊有長度。求最小生成樹總權重。多測試案例，n=0 結束。

Prim 算法（鄰接矩陣）

適合稠密圖，O(n²)。

double prim(int n, const vector<vector<double>> &g) {
    vector<double> dist(n, 1e100);
    vector<bool> vis(n, false);
    dist[0] = 0; double ans = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int j = 0; j < n; ++j)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        vis[u] = true; ans += dist[u];
        for (int v = 0; v < n; ++v)
            if (!vis[v] && g[u][v] < dist[v]) dist[v] = g[u][v];
    }
    return ans;
}

Kruskal 算法（邊排序 + 並查集）

適合稀疏圖，O(E log E)。

struct Edge { int u, v; double w; };
double kruskal(int n, vector<Edge> edges) {
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b){ return a.w < b.w; });
    vector<int> fa(n); iota(fa.begin(), fa.end(), 0);
    function<int(int)> find = [&](int x){ return fa[x]==x?x:fa[x]=find(fa[x]); };
    double ans = 0; int cnt = 0;
    for (auto &e : edges) {
        int fu = find(e.u), fv = find(e.v);
        if (fu != fv) { fa[fu] = fv; ans += e.w; if (++cnt == n-1) break; }
    }
    return ans;
}

完整程式（雙版本）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    while (cin >> n, n) {
        vector<vector<double>> g(n, vector<double>(n));
        for (int i = 0; i < n*(n-1)/2; ++i) {
            int a, b; double c; cin >> a >> b >> c; --a; --b;
            g[a][b] = g[b][a] = c;
        }
        cout << fixed << setprecision(2) << prim(n, g) << '\n';
    }
}

選擇建議

• n ≤ 100 完全圖 → Prim 更簡潔快速。
• 邊數較少或需輸出具體邊 → Kruskal。