【通电】第十一届蓝桥杯省赛第二次模拟（并查集+Kruskal）

青旅半醒 2022-12-03 09:13 140阅读 0赞

【问题描述】  
  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算法）][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++;
    			merge(start, end);
    			sum += edges[i].cost;
    			if(cnt == n - 1) { 
    				break;
    			}
    		}
    	}
    	printf("%.2f", sum);
    	return 0;
    }

[C_C_A_Kruskal]: https://blog.csdn.net/Cyril_KI/article/details/107942299