【Prim算法】通电

题目

通电 - 蓝桥云课

---

题目描述

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

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

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

小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为( $x_1, y_1$ ) 高度为 $h_1$ 的村庄与坐标为 ( $x_2, y_2$ ) 高度为 $h_2$ 的村庄之间连接的费用为

$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}+(h_1-h_2)^2$

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

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

输入描述

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

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

其中， $1 \leq n \leq 1000，0 \leq x, y, h \leq 10000$ 。

输出描述

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

输入输出样例

示例

输入

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

输出

17.41

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M

解题

方法一：朴素Prim算法

思路

本题是最小生成树裸题，每两点之间都有一条无向边，是稠密图，直接用朴素版Prim算法求解即可。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n;
    static int[][] poses;

    static double getDist(int a, int b) {
        return Math.sqrt(Math.pow(poses[a][0] - poses[b][0], 2) + 
                Math.pow(poses[a][1] - poses[b][1], 2)) + 
                Math.pow(poses[a][2] - poses[b][2], 2);
    }

    static double prim() {
        double[] dists = new double[n + 1];
        Arrays.fill(dists, INF);
        boolean[] vis = new boolean[n + 1];
        double res = 0.0;
        for (int i = 0; i < n; ++i) {
            int mn = -1;
            for (int j = 1; j <= n; ++j) {
                if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
            }
            if (i > 0) {
                if (dists[mn] == INF) return INF;
                res += dists[mn];
            }
            for (int j = 1; j <= n; ++j) {
                dists[j] = Math.min(dists[j], getDist(j, mn));
            }
            vis[mn] = true;
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        poses = new int[n + 1][3];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            poses[i][0] = (int) in.nval;
            in.nextToken();
            poses[i][1] = (int) in.nval;
            in.nextToken();
            poses[i][2] = (int) in.nval;
        }
        System.out.printf("%.2f\n", prim());
    }
}