思路
kruskal求最小生成树的过程本质上是连通块从 n减少到1的过程
此题可以将题目抽象为求联通块的数目小于等于k时,集合的边的最大值,因此只需用kruskal求出连通块的数量在k时,此时的边的长度即可,连通块的数量为k,加边的操作数为n-k
C++ 代码
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 100010;
vector<pair<double, double>> tmp;
int p[N];
double get_path(int i, int j) {
double x1 = tmp[i].first, y1 = tmp[i].second, x2 = tmp[j].first, y2 = tmp[j].second;
double g = pow(x1 - x2, 2) + pow(y1 - y2, 2);
return sqrt(g);
}
struct node {
int a, b;
double c;
bool operator <(const node g) {
return c < g.c;
}
}tr[N];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n + 10; i++) p[i] = i;
for (int i = 0; i < n; i++) {
double a, b;
cin >> a >> b;
tmp.push_back({ a,b });
}
int idx = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double g = get_path(i, j);
tr[idx++] = { i,j,g };
}
}
sort(tr, tr + idx);
int cnt = 0;
double res = 0;
for (int i = 0; i < idx; i++) {
int a = tr[i].a, b = tr[i].b;
if (n - k == cnt) {
break;
}
if (find(a) == find(b)) continue;
p[find(a)] = find(b);
cnt++;
res = tr[i].c;
}
printf("%.2lf", res);
return 0;
}