AcWing 1145. 北极通讯网络-求Kruskal中MST的倒数第k大的边
原题链接
中等
作者:
_T_
,
2022-02-06 14:19:40
,
所有人可见
,
阅读 161
C++ 代码
//我不知道这样理解有没有问题“求Kruskal中MST的倒数第k大的边”,当然k=0 特判一下即可
//先生成最小生成树,删除前k条大边,再输出最大的边即为d
#include <iostream>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 510, M = N * N / 2;
int n, m, k; // 点数、边数、卫星数
struct Edge {
int a, b;
double w;
bool operator< (const Edge &e) {
return w < e.w;
}
} edges[M];
PII q[N];
int p[N];
double get_dist(PII a, PII b) {
int dx = a.x - b.x, dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
//本题就是求MST 中Kruskal倒数第k条大小
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
edges[m++] = {i, j, get_dist(q[i], q[j])};
for (int i = 0; i < n; i++) p[i] = i;
sort(edges, edges + m);
double res = 0;
int cnt =0;
for (int i = 0; i < m; i++) {
if (cnt >=n- (k==0?1:k)) break;
int a = edges[i].a, b = edges[i].b;
double w = edges[i].w;
a = find(a), b = find(b);
if (a != b) {
p[a] = b;
cnt++;
res = w;//
}
}
printf("%.2lf\n", res);
return 0;
}