算法1
(Kurskal)
从小到大贪心即可。
C++ 代码
#include <bits/stdc++.h>
#define For(i, a, b) for(register int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for(register int i = (a); i >= (b); --i)
#define INF 0x3f3f3f3f
#define LL long long
#define MaxN 510
#define Sqr(x) ((x) * (x))
#define D(A, B) ((double)Sqr(X[A] - X[B]) + Sqr(Y[A] - Y[B]))
using namespace std;
int T, N, M, K, X[MaxN], Y[MaxN], Fa[MaxN], Rest;
struct Xjh {int U, V; double Dis;} E[MaxN * MaxN];
bool Cmp(Xjh A, Xjh B) {return A.Dis < B.Dis;}
int Find(int x) {return x == Fa[x] ? x : Fa[x] = Find(Fa[x]);}
bool Unite(int x, int y) {
if((x = Find(x)) == (y = Find(y))) return 0;
Fa[x] = y; return 1;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &K, &N); M = 0; Rest = N - K;
For(i, 1, N) Fa[i] = i, scanf("%d%d", &X[i], &Y[i]);
For(i, 1, N) For(j, i + 1, N) E[++M] = (Xjh){i, j, D(i, j)};
sort(E + 1, E + 1 + M, Cmp);
if(Rest <= 0) {puts("0"); continue;}
For(i, 1, M) if(!(Rest -= Unite(E[i].U, E[i].V))) {
printf("%.2lf\n", sqrt((double)E[i].Dis)); break;
}
}
return 0;
}