北极通讯网络
题意
北极的某区域共有n座村庄，每座村庄的坐标用一对整数(x,y) 表示。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机，且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。
不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d 就可以用该型号的无线电收发机直接通讯，d 值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。
现在有k台卫星设备，请你编一个程序，计算出应该如何分配这 k 台卫星设备，才能使所拥有的无线电收发机的 d值最小，并保证每两座村庄之间都可以直接或间接地通讯。
例如，对于下面三座村庄：
其中∣ A B ∣ = 10 , ∣ B C ∣ = 20 , ∣ A C ∣ = 10 5 ≈ 22.36 ∣AB∣=10,∣BC∣=20,∣AC∣=10\sqrt{5}≈22.36
如果没有任何卫星设备或只有1 11台卫星设备(k=0 或k=1)，则满足条件的最小的d=20，因为 A和 B，B和 C 可以用无线电直接通讯；而 A 和 C可以用 B中转实现间接通讯(即消息从 A传到 B，再从 B 传到 C；
如果有2台卫星设备(k=2)，则可以把这两台设备分别分配给B和C，这样最小的d dd可取10 1010，因为A AA和B之间可以用无线电直接通讯；B和C之间可以用卫星直接通讯；A和C可以用B中转实现间接通讯。
如果有3台卫星设备，则A ,B,C两两之间都可以直接用卫星通讯，最小的d可取0。
思路
由题意可知，k个卫星设备可以使得k−1 条通讯线路的 d 值变成 0，那么只需要将图中每个点之间的距离求出来，并求出最小生成树，然后去掉最小生成树中k−1条权值最大的边之后，剩下的边中权值最大的即为所求的 d
代码
// Author：zzqwtcc // Problem: 北极通讯网络 // Contest: NowCoder // Time：2021-10-20 19:59:44 // URL: https://ac.nowcoder.com/acm/contest/958/B // Memory Limit: 65536 MB // Time Limit: 2000 ms #include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) //#define debug(x,y) cerr << (x) << " == " << (y) << endl; #define endl '\n' using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } template<typename T,typename S>inline void debug(S s,T t){cerr << s << " " << t << endl;} template<typename T>inline void debug(T t){cerr << t << endl;} // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 600; int n, k; struct Node{ double x,y; }node[N]; double dist[N][N]; bool vis[N]; double d[N]; vector<double>vec; double get_dis(const Node &a,const Node &b){ return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } void prim(){ rep(i,1,n)d[i] = DBL_MAX; d[1] = 0; int cnt = 0; for(int i = 1; i <= n;++i){ int t = -1; for(int j = 1; j <= n;++j){ if(!vis[j] && (t == - 1 || d[t] > d[j]))t = j; } vec.push_back(d[t]); vis[t] = true; for(int j = 1; j <= n;++j){ d[j] = min(d[j], dist[t][j]); } } } void solve() { cin >> n >> k; for(int i = 1; i <= n;++i){ cin >> node[i].x >> node[i].y; } for(int i = 1; i <= n;++i){ for(int j = i + 1; j <= n;++j){ double dis = get_dis(node[i],node[j]); dist[i][j] = dist[j][i] = dis; } } prim(); sort(vec.begin(),vec.end()); reverse(vec.begin(),vec.end()); if(k <= 1){ printf("%.2lf\n",vec[0]); } else if(k < n){ printf("%.2lf\n",vec[k - 1]); } else cout << 0 << endl; } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
