题解 | #Freckles#

迪杰斯塔拉算法的简单应用
#include<iostream>
#include<cstdio>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

int father[105];

struct node {
	int order;  //用输入的序号来单独做标记
	float x;
	float y;

};

struct Edge {
	int a, b;
	float length;

};

bool compare(Edge lhs, Edge rhs) {
	return lhs.length < rhs.length;
}


void Init(int n) {
	for (int i = 1; i <= n; i++) {
		father[i] = i;
	}
}

int Find(int x) {
	if (x != father[x])
		father[x] = Find(father[x]);
	return father[x];

}

void Union(int x, int y, float & total,float length) {
	x = Find(x);
	y = Find(y);
	if (x != y) {   //将两个节点合并
		father[y] = x;
		total = total + length;
	}



}



int main() {
	vector<node> vec1;
	vector<Edge> vec2;
	int n;
	cin >> n;
	Init(n);
	for (int i = 1; i <= n; i++) {
		node temp;
		cin >> temp.x >> temp.y;
		temp.order = i;
		vec1.push_back(temp);
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			Edge edge;
			edge.a = vec1[i].order;
			edge.b = vec1[j].order;
			edge.length = sqrt((vec1[i].x - vec1[j].x) * (vec1[i].x - vec1[j].x) + (vec1[i].y - vec1[j].y) * (vec1[i].y - vec1[j].y));

			vec2.push_back(edge);
		}
	}
	sort(vec2.begin(), vec2.end(), compare);
	float total = 0;
	for (int i = 0; i < n * (n - 1) / 2; i++) {
		Union(vec2[i].a, vec2[i].b, total, vec2[i].length);
	}
	printf("%.2f\n", total);


	return 0;


}