Kruskal维护连通块个数
本题一个关键而巧妙的点是想这个卫星要建在哪个点上，我们可以发现，d=+∞时，卫星k=0，k>=n时，d=0，再分析可知，d越大，k越小，由此我们想到二分d，看当前需要的k是不是小于题目给的k
但是怎么得到这个“当前需要的k”呢？答案是考虑当前的连通块数量，比如现在图上有3个连通块，就要有3个卫星才能维持全图通信。
故我们用Kru算法，从小到大贪心枚举到当前的第x条边时，连通块的数量是不是小于k即可。
Code：
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 510;
typedef pair<int, int> PII;
PII q[N];
int n, k;
int p[N];
int find(int x) {
if (p[x] != x)p[x] = find(p[x]);
return p[x];
}
struct Edge {
int a, b;
double w;
bool operator<(const Edge&other)const { return w < other.w; }
}e[N*N];
int cnt;
double get_dist(PII a, PII b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx*dx + dy * dy);
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++)cin >> q[i].x >> q[i].y;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)e[cnt++] = { i,j,get_dist(q[i],q[j]) };
sort(e, e + cnt);
int block = n;
for (int i = 1; i <= n; i++)p[i] = i;
if (k >= n) {
cout << 0; return 0;
}
for (int i = 0; i < cnt; i++) {
int a = find(e[i].a), b = find(e[i].b);
double w = e[i].w;
if (a != b) {
p[a] = b;
block--;
if (block <= k) {
printf("%.2lf", e[i].w);
return 0;
}
}
}
}