侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【Prim算法】通电

GabrielxD
2023-03-16 / 0 评论 / 0 点赞 / 186 阅读 / 856 字
温馨提示:
本文最后更新于 2023-03-16,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

通电 - 蓝桥云课


题目描述

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

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

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

小明测量了所有村庄的位置(坐标)和高度,如果要连接两个村庄,小明需要花费两个村庄之间的坐标距离加上高度差的平方,形式化描述为坐标为( x1,y1x_1, y_1 ) 高度为 h1h_1 的村庄与坐标为 ( x2,y2x_2, y_2 ) 高度为 h2h_2 的村庄之间连接的费用为

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

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

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

输入描述

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

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

其中, 1n10000x,y,h100001 \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());
    }
}
0

评论区