範例程式碼 uva10369
//uva10369
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#define MAXV (500+1)
#define MAXE (500*500+1)
using namespace std;
double x[MAXV], y[MAXV];
int S, P, E, totS;
int fa[MAXV];
struct edge{
int n1, n2;
double dis;
void init (int n1, int n2) {
this->n1 = n1;
this->n2 = n2;
dis = sqrt((x[n1] - x[n2]) * (x[n1] - x[n2]) + (y[n1] - y[n2]) * (y[n1] - y[n2]));
}
}e[MAXE];
bool ecmp (edge e1, edge e2) {
return e1.dis < e2.dis;
}
int find_set(int n) {
if (fa[n] == n)
return n;
else
return fa[n] = find_set(fa[n]);
}
void union_set(int x, int y) {
int rx = find_set(x);
int ry = find_set(y);
if (rx != ry) {
fa[ry] = rx;
totS --;
}
}
double kruskal() {
int i, n1, n2;
double ans = 0;
for (i = 0; i < E && totS > S; i++) {
n1 = e[i].n1;
n2 = e[i].n2;
union_set(n1, n2);
ans = max(ans, e[i].dis);
}
return ans;
}
int main() {
int i, j, t;
scanf("%d", &t);
while (t --) {
scanf("%d %d", &S, &P);
for (i = 0; i < P; i++)
scanf("%lf %lf",&x[i],&y[i]);
for (E = 0, i = 0; i < P; i++)
for (j = i + 1; j < P; j++)
e[E++].init(i, j);
totS = P;
sort(e,e + E,ecmp);
for (i = 0; i < P; i++)
fa[i] = i;
printf("%.2lf\n",kruskal());
}
return 0;
}