题解 | #Freckles#

//土尔逊Torson 编写于2023/07/06
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdlib.h>
#define N 101

using namespace std;

float res13601;

struct FrecklesPos {
	float x;
	float y;
};

struct FLine {
	int from;
	int to;
	float weight;
	inline bool operator <(const FLine &g)const {
		return weight < g.weight;
	}
};

vector<FLine> graph13601;
vector<FrecklesPos> vec13601;

int father13601[N];
int height13601[N];

void init13601(int n) {
	for (int i = 0; i <= n; ++i) {
		father13601[i] = i;
		height13601[i] = 0;
	}
	graph13601.clear();
	vec13601.clear();
	res13601 = 0;
}

float getdis(FrecklesPos a, FrecklesPos b) {
	return pow((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y), 0.5);
}

int find13601(int x) {
	if (x != father13601[x]) {
		father13601[x] = find13601(father13601[x]);
	}
	return father13601[x];
}

void Union13601(int x, int y, float weight) {
	x = find13601(x);
	y = find13601(y);
	if (x != y) {
		res13601 += weight;
		if (height13601[x] > height13601[y]) {
			father13601[y] = x;
		}
		else if (height13601[x] < height13601[y]) {
			father13601[x] = y;
		}
		else {
			father13601[x] = y;
			height13601[y]++;
		}
	}
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		init13601(n);
		FrecklesPos p;
		FLine g;
		for (int i = 0; i < n; ++i) {
			scanf("%f%f", &p.x, &p.y);
			vec13601.push_back(p);
		}

		for (int i = 0; i < vec13601.size() - 1; ++i) {
			for (int j = i + 1; j < vec13601.size(); ++j) {
				g.from = i;
				g.to = j;
				g.weight = getdis(vec13601[i], vec13601[j]);
				graph13601.push_back(g);
			}
		}
		sort(graph13601.begin(), graph13601.end());
		for (int i = 0; i < graph13601.size(); ++i) {
			Union13601(graph13601[i].from, graph13601[i].to, graph13601[i].weight);
		}
		printf("%.2f\n", res13601);
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")