北极通讯网络

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1587 字
完全图Kruskal，连通块降到k时的边长
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1487
// 题意：n 个村庄有坐标，k 台卫星设备可使装备它的村庄之间无视距离直连，求最小无线电通信半径 d，保留两位小数。
// 思路：村庄间两两连边建完全图跑 Kruskal，连通块数降到 k 时最后加入的那条边长度就是答案，等价于最小生成树的第 n-k 条边。
// 复杂度：O(n^2 log n) 时间 / O(n^2) 空间
// 易错点：k>=n 时不需要任何无线电边，答案直接为 0.00；距离必须用 double 开平方，不要拿平方值当答案输出。
#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int u, v;
    double w;
};
struct DSU{
    int p[505];
    void init(int n){
        for(int i = 1; i <= n; i++) p[i] = i;
    }
    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    bool unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return false;
        p[a] = b;
        return true;
    }
};
int main(){
    int n, k;
    if(!(cin >> n >> k)) return 0;
    vector<double> x(n + 1), y(n + 1);
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    if(k >= n){
        cout << fixed << setprecision(2) << 0.0 << '\n';
        return 0;
    }
    vector<Edge> e;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            double dx = x[i] - x[j];
            double dy = y[i] - y[j];
            e.push_back({i, j, sqrt(dx * dx + dy * dy)});
        }
    }
    sort(e.begin(), e.end(), [](const Edge &a, const Edge &b){
        return a.w < b.w;
    });
    DSU dsu;
    dsu.init(n);
    int cnt = n;
    double ans = 0;
    for(size_t i = 0; i < e.size(); i++){
        if(dsu.unite(e[i].u, e[i].v)){
            ans = e[i].w;
            cnt--;
            if(cnt == k) break;
        }
    }
    cout << fixed << setprecision(2) << ans << '\n';
    return 0;
}
北极通讯网络

正文

一本通·提高篇的其它内容
