题解 | #Freckles#

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

const int MAXN = 5000;

class freckle{
public:
	int num;//编号
	double x, y;
	freckle(int a, double b, double c):num(a),x(b),y(c){}
};

class Edge{
public:
	int from;
	int to;
	double length;
	Edge():from(0),to(0),length(0){}
	Edge(int a, int b, double c):from(a),to(b),length(c){}
	bool operator<(const Edge &e) const {
		return length < e.length;
	}
};

Edge edge[MAXN];

int Find(int x, int* parent){
	if(*(parent+x) < 0){
		return x;
	}
	return Find(*(parent+x), parent);
}

bool Union(int x, int y, int* parent){
	x = Find(x, parent);
	y = Find(y, parent);
	if(x != y){
		if(*(parent+x) > *(parent+y)){
			*(parent+x) = y;
		}else if(*(parent+x) < *(parent+y)){
			*(parent+y) = x;
		}else{
			*(parent+y) = x;
			(*(parent+x))--;
		}
		return true;
	}
	return false;
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		if(n == 1){
			printf("0\n");
			continue;
		}
		int parent[n];
		memset(parent, -1, sizeof(parent));
		double x, y;
		vector<freckle> v;
		for(int i=0; i<n; i++){
			scanf("%lf%lf", &x, &y);
			v.push_back(freckle(i, x, y));
		}
		int maxn = n*(n-1)/2;
		int k = 0;//用来初始化edge 
		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				edge[k].from = i;
				edge[k].to = j;
				edge[k++].length = sqrt(pow(v[i].x-v[j].x, 2) + pow(v[i].y-v[j].y, 2));
			}
		}
		sort(edge, edge+maxn);
		double sum = 0.0;
		for(int i=0; i<maxn; i++){
			if(Union(edge[i].from, edge[i].to, parent)){
				sum += edge[i].length;
			}
		}
		printf("%.2lf\n",sum);
	}
	return 0;
}