题解 | Freckles

//有些时候不要太死板了，数据结构复杂的情况下，想存关系并不是非得用复杂的结构体来索引，可以都存入数组中，用数组下标即int类型来索引
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
const int N = 110;
int p[N];
int find(int x) {
	if (p[x] != x)p[x] = find(p[x]);
	return p[x];
}
struct node {
	double x, y;
	node(int x, int y) {
		this->x = x, this->y = y;
	}
	node() {

	}
};

struct edge {
	int x, y;
	double	weight;//这里点的坐标用int并不是坐标的值而是坐标在vector数组中的索引
	edge(int x, int y, double weight) {
		this->x = x, this->y = y, this->weight = weight;
	}
	//要使用Kruskal算法，边要排序，所以要进行运算符重载
	bool operator<(const edge& cmp)const {
		return this->weight < cmp.weight;
	}
};
int main() {
	int n;
	cin >> n;
	vector<node> allnode;//其实在allnode中的索引也就代表结点的编号
	vector<edge>e;
	int k = n;
	while (k--) {
		double x, y;
		cin >> x >> y;
		allnode.push_back(node(x, y));
	}
	//并查集初始化
	for (int i = 0; i < allnode.size(); i++) {
		p[i] = i;
	}

	//循环生成所有的边
	for(int i=0;i<allnode.size();i++)
		for (int j = 0; j < allnode.size(); j++) {
			if (i == j)continue;
			double weight = sqrt((allnode[i].x - allnode[j].x) * (allnode[i].x - allnode[j].x) + (allnode[i].y - allnode[j].y) * (allnode[i].y - allnode[j].y));
			e.push_back(edge(i, j, weight));
		}

	sort(e.begin(), e.end());
	double res = 0;
	int count = 0;
	for (int i = 0; i < e.size(); i++) {
		if (find(e[i].x) != find(e[i].y)) {
			p[find(e[i].x)] = find(e[i].y);
			res += e[i].weight;
			count++;
		}
		if (count == n - 1)break;
	}
	printf("%.2lf\n", res);
	return 0;
}
//还是有点麻烦的，好烦呀，我怎么那么菜