[蓝桥杯]通电

通电

题目描述

2015 年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。

这一次，小明要帮助 nn 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。

现在，这 nn 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。

小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为(x1,y1x1​,y1​) 高度为 h1h1​ 的村庄与坐标为 (x2,y2x2​,y2​) 高度为 h2h2​ 的村庄之间连接的费用为

(x1−x2)2+(y1−y2)2+(h1−h2)2(x1​−x2​)2+(y1​−y2​)2+(h1​−h2​)2​

高度的计算方式与横纵坐标的计算方式不同。

由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 nn 个村庄都通电。

输入描述

输入的第一行包含一个整数 nn ，表示村庄的数量。

接下来 nn 行，每个三个整数 x,y,hx,y,h，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。

其中，1≤n≤1000，0≤x,y,h≤100001≤n≤1000，0≤x,y,h≤10000。

输出描述

输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。

输入输出样例

示例

输入

4
1 1 3
9 9 7
8 8 6
4 5 4

输出

17.41

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 1434  |  总提交次数: 1697  |  通过率: 84.5%

难度: 困难   标签: 2020, 最小生成树, 省模拟赛

C++实现村庄通电问题：最小生成树（Prim算法）

算法思路

该问题本质是求解​​最小生成树​​（MST），需要连接所有村庄，使总费用最小。费用计算公式为：
费用 = √[(x₁-x₂)² + (y₁-y₂)²] + (h₁-h₂)²
其中：

• 前半部分为平面欧几里得距离（需开平方）
• 后半部分为高度差的平方

采用 ​​Prim算法​​（适合稠密图），步骤：

1. 从发电站（村庄0）开始初始化
2. 每次选择当前距离生成树集合最近的未连接村庄
3. 更新该村庄邻接点与集合的最小距离
4. 重复直至所有村庄连通

---

C++代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <climits>
using namespace std;struct Village {double x, y, h;
};double calculateCost(const Village& a, const Village& b) {double dx = a.x - b.x;double dy = a.y - b.y;double dh = a.h - b.h;return sqrt(dx*dx + dy*dy) + dh*dh; // 关键公式
}int main() {int n;cin >> n;vector<Village> villages(n);// 读取村庄数据for (int i = 0; i < n; ++i) {cin >> villages[i].x >> villages[i].y >> villages[i].h;}vector<double> minDist(n, 1e18); // 初始化为极大值vector<bool> visited(n, false);double totalCost = 0.0;// 从发电站（0号村庄）开始minDist[0] = 0;for (int i = 0; i < n; ++i) {int u = -1;// 寻找最近的未访问村庄for (int j = 0; j < n; ++j) {if (!visited[j] && (u == -1 || minDist[j] < minDist[u])) {u = j;}}if (minDist[u] == 1e18) { // 存在未连通村庄cout << "-1" << endl;return 0;}visited[u] = true;totalCost += minDist[u];// 更新邻接村庄的最小距离for (int v = 0; v < n; ++v) {if (!visited[v]) {double cost = calculateCost(villages[u], villages[v]);if (cost < minDist[v]) {minDist[v] = cost;}}}}cout << fixed << setprecision(2) << totalCost << endl;return 0;
}

代码解析

1. ​​数据结构​​

   • Village结构体存储坐标(x,y)和高度(h)
   • minDist数组：记录各村庄到生成树集合的最小距离
   • visited数组：标记村庄是否已连接

2. ​​核心函数​​

   double calculateCost(const Village& a, const Village& b) {double dx = a.x - b.x;double dy = a.y - b.y;double dh = a.h - b.h;return sqrt(dx*dx + dy*dy) + dh*dh; // 平面距离 + 高度差平方
   }

3. ​​Prim算法流程​​

   • ​​初始化​​：将发电站（0号村庄）距离设为0
   • ​​贪心选择​​：每次选取minDist最小的未访问村庄
   • ​​更新距离​​：用新加入村庄更新邻接点距离
   • ​​终止条件​​：所有村庄被访问

---

实例验证

输入样例：

4
1 1 3
9 9 7
8 8 6
4 5 4

计算过程：

1. 初始选择村庄0(1,1,3)，距离集合为0
2. 选择村庄3(4,5,4)，费用=√(3²+4²)+(4-3)²=5+1=6
3. 选择村庄2(8,8,6)，费用=√(4²+3²)+(6-4)²=5+4=9
4. 选择村庄1(9,9,7)，费用=√(1²+1²)+(7-6)²≈1.41+1=2.41
5. 总费用=6+9+2.41=17.41

输出结果：17.41 ✅

---

关键测试点

测试场景	预期结果	验证要点
单村庄 (n=1)	0.00	边界条件处理
所有村庄高度相同	纯平面距离求和	高度计算正确性
所有村庄坐标相同	0.00	零距离处理
线性排列村庄	相邻距离求和	连接顺序正确性
高度差主导费用	优先选低高度差	贪心策略有效性

---

优化建议

1. ​​堆优化Prim​​（时间复杂度O(ElogV)）

   priority_queue<pair<double, int>> pq;
   pq.push({0, 0});
   while (!pq.empty()) {int u = pq.top().second;pq.pop();// ...更新邻接点距离并加入堆
   }

2. ​​计算优化​​

   • 预先计算所有点对距离 → 空间换时间（O(n²)空间）
   • 高度差平方改用整数计算避免浮点误差

3. ​​异常处理​​

   • 添加连通性检查（未连通时返回-1）
   • 浮点数精度控制（如用1e-8容差）

---

注意事项

1. ​​浮点精度问题​​

   • 比较浮点数时使用容差：abs(a-b) < 1e-8
   • 输出时用setprecision(2)控制小数位

2. ​​大数处理​​

   • 坐标范围0~10000时，最大距离≈√(2×10000²)=14142，需用double存储

3. ​​算法选择​​

   • 村庄数≤1000 → Prim的O(n²)优于Kruskal的O(n²logn)
   • 若村庄数>10⁴，需改用堆优化Prim或Kruskal