【问题描述】 2015年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。 这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。 现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。 小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为 (x_1, y_1) 高度为 h_1 的村庄与坐标为 (x_2, y_2) 高度为 h_2 的村庄之间连接的费用为： sqrt((x_1-x_2)(x_1-x_2)+(y_1-y_2)(y_1-y_2))+(h_1-h_2)*(h_1-h_2)。 在上式中 sqrt 表示取括号内的平方根。请注意括号的位置，高度的计算方式与横纵坐标的计算方式不同。 由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。 【输入格式】 输入的第一行包含一个整数 n ，表示村庄的数量。 接下来 n 行，每个三个整数 x, y, h，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。 【输出格式】 输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。 【样例输入】 4 1 1 3 9 9 7 8 8 6 4 5 4 【样例输出】 17.41 【评测用例规模与约定】 对于 30% 的评测用例，1 <= n <= 10； 对于 60% 的评测用例，1 <= n <= 100； 对于所有评测用例，1 <= n <= 1000，0 <= x, y, h <= 10000。
思路分析：题目的意思大概是说：现在我有n个结点，每个结点都有三个属性，通过两个结点的三个属性可以算出这两个结点相连边的权值大小。题目要求所有n个村庄全部通电，就是让所有点都连通起来，而又要求代价最小，其实就是求该无向网的最小生成树。求最小生成树的算法常见的有prim算法和Kruskal算法，我比较熟悉后一种，所以这里就选择用Kruskal算法来解决该问题。 Kruskal算法的具体讲解可参考：【灾后重建】蓝桥杯第六届省赛C/C++大学A组（并查集+Kruskal算法）
这里就直接上代码了：
#include<bits/stdc++.h> using namespace std; const int maxn = 1002; int n, par[maxn]; //定义结点 struct node { int x; int y; int h; }nodes[maxn]; //定义边 struct edge { int start; int end; float cost; }edges[maxn * (maxn - 1) / 2]; //计算代价 float cost(node a, node b) { float x = a.x - b.x; float y = a.y - b.y; float h = a.h - b.h; return sqrt(x * x + y * y) + h * h; } //并查集的一些操作 //求根结点 int get_root(int a) { if(par[a] != a) { par[a] = get_root(par[a]); } return par[a]; } //查询是否在同一集合中 bool query(int a,int b) { return get_root(a) == get_root(b); } //合并两个结点 void merge(int a,int b) { par[get_root(a)] = get_root(b); } //初始化 void init(int n) { for(int i = 1;i <= n;i++) { par[i] = i; } } bool cmp(edge x, edge y) { return x.cost < y.cost; } int main() { cin >> n; init(n); int x, y, h; int index = 0; for(int i = 0; i < n; i++) { cin >> nodes[i].x >> nodes[i].y >> nodes[i].h; } //生成所有边的序号，其实就是组合数 for(int i = 0; i < n; i++) { for(int j = 0; j < n && j != i; j++) { edges[index].start = i; edges[index].end = j; edges[index].cost = cost(nodes[i], nodes[j]); index++; } } //按cost从小到大排序 sort(edges, edges + index, cmp); float sum = 0.0; int cnt = 0; //在不形成环的条件下依次选择n - 1条边，并把它们的权值相加输出 for(int i = 0; i < index; i++) { int start = edges[i].start; int end = edges[i].end; if(get_root(start) != get_root(end)) { cnt++; sum += edges[i].cost; if(cnt == n - 1) { break; } } } printf("%.2f", sum); return 0; }