HDOJ 1875 暢通工程再續：Kruskal/Prim 帶邊長限制的 MST

題目差異

同 HDU 1233，但邊長必須在 [10, 1000] 範圍內才可選。若無法連通所有點輸出 oh!，否則輸出總長度 × 100 保留一位小數。

Kruskal 更適合

直接過濾邊：讀入時若長度不在區間內則不加入邊列表。
跑標準 Kruskal，最後檢查連通塊數是否為 1。

Kruskal 代碼

#include <bits/stdc++.h>
using namespace std;
struct Edge { int u, v; double w; };
int find(vector<int> &fa, int x) { return fa[x]==x?x:fa[x]=find(fa, fa[x]); }
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<pair<double,double>> pt(n+1);
        for (int i = 1; i <= n; ++i) cin >> pt[i].first >> pt[i].second;
        vector<Edge> edges;
        for (int i = 1; i <= n; ++i)
            for (int j = i+1; j <= n; ++j) {
                double dx = pt[i].first - pt[j].first;
                double dy = pt[i].second - pt[j].second;
                double d = sqrt(dx*dx + dy*dy);
                if (d >= 10 - 1e-9 && d <= 1000 + 1e-9)
                    edges.push_back({i, j, d});
            }
        sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b){ return a.w < b.w; });
        vector<int> fa(n+1); iota(fa.begin(), fa.end(), 0);
        double ans = 0; int cnt = 0;
        for (auto &e : edges) {
            int fu = find(fa, e.u), fv = find(fa, e.v);
            if (fu != fv) { fa[fu] = fv; ans += e.w; if (++cnt == n-1) break; }
        }
        if (cnt != n-1) cout << "oh!\n";
        else cout << fixed << setprecision(1) << ans * 100 << '\n';
    }
    return 0;
}

Prim 版本注意點

Prim 需在松弛時判斷邊長限制，且 dist 數組用 double，INF 設為 1e100。
最後同樣檢查是否所有點都被訪問。

複雜度

Kruskal O(E log E)，E ≤ n²/2 ≈ 5000，極快。