[蓝桥杯]通电-EW帮帮网

通电

题目描述

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 位小数，表示答案。

输入输出样例

示例

输入

输出

17.41

运行限制

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

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

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

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

算法思路

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

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

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

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

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;
}

代码解析

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

核心函数

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; // 平面距离 + 高度差平方
}

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

实例验证

输入样例：

计算过程：

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

输出结果：17.41 ✅

关键测试点

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

优化建议

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

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

计算优化
- 预先计算所有点对距离 → 空间换时间（O(n²)空间）
- 高度差平方改用整数计算避免浮点误差
异常处理
- 添加连通性检查（未连通时返回-1）
- 浮点数精度控制（如用1e-8容差）

注意事项

浮点精度问题
- 比较浮点数时使用容差：abs(a-b) < 1e-8
- 输出时用setprecision(2)控制小数位
大数处理
- 坐标范围0~10000时，最大距离≈√(2×10000²)=14142，需用double存储
算法选择
- 村庄数≤1000 → Prim的O(n²)优于Kruskal的O(n²logn)
- 若村庄数>10⁴，需改用堆优化Prim或Kruskal

[蓝桥杯]通电