uva10034

题意：最小生成树

思路：kruskal

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
using namespace std;
const int N = 105;
double x[N], y[N];
struct edge {
	double x, y, d;
}e[N*N];
int f[N];
double ans;
double dis(double x1, double y1, double x2, double y2) {
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
int n;
int num;
int cmp(edge a, edge b) {
	return a.d < b.d;
}
int find(int x) {
	return (x == f[x])?x:find(f[x]);
}
void uni(int a, int b) {
	
	f[a] = find(b);
}

void ki() {
	ans = 0;
	for(int i=0; i<n; i++) f[i] = i;
	for(int i=0; i<num; i++) {
		int a = find(e[i].x);
		int b = find(e[i].y);
		if(a != b) {
			uni(a,b);
			ans += e[i].d;
		}
	}
	printf("%.2lf\n", ans);
}

int main() {
	int cas; 
	scanf("%d", &cas);
	while(cas--) {
		num = 0;
		scanf("%d", &n);
		for(int i=0; i<n; i++) {
			scanf("%lf%lf", &x[i], &y[i]);
		}
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++) {
				if(i != j) {
				e[num].x = i;
				e[num].y = j;
				e[num++].d = dis(x[i], y[i], x[j], y[j]);
				}
			}
		sort(e, e+num, cmp);
		ki();
		if(cas) printf("\n");
	}

	return 0;
}