当前位置: 首页 > news >正文

华为od-C卷200分题目6 - 5G 网络建设

华为od-C卷200分题目6 - 5G 网络建设

题目描述
现需要在某城市进行 5G 网络建设,已经选取 N 个地点设置 5G 基站,编号固定为 1 到 N,接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通,不同基站之间架设光纤的成本各不相同,且有些节点之间已经存在光纤相连,请你设计算法,计算出能联通这些基站的最小成本是多少。

注意,基站的联通具有传递性,即基站 A 与基站 B 架设了光纤基站 B 与基站 C 也架设了光纤,则基站 A 与基站 C 视为可以互相联通

输入
第一行输入表示基站的个数 N,其中 0 < N <= 20

第二行输入表示具备光纤直连条件的基站对的数目 M,其中 0 < M < N * (N - 1) / 2

第三行开始连续输入 M 行数据,格式为 X Y Z P,其中 X Y 表示基站的编号,0 < X <= N, 0 < Y <= N 且 X 不等于 Y, Z 表示在 X Y 之间架设光纤的成本,其中 0 < Z < 100,P 表示是否已存在光纤连接,0 表示未连接, 1 表示已连接。

输出
如果给定条件,可以建设成功互联互通的 5G 网络,则输出最小的建设成本,

如果给定条件,无法建设成功互联互通的 5G 网络,则输出-1

样例输入 复制
3
3
1 2 3 0
1 3 1 0
2 3 5 0
样例输出 复制
4
提示
只需要在 1,2 以及 2,3 基站之间铺设光纤,其成本为 3+1=4

import java.util.*;class Point {int parent;int size = 1;int cost = 0;public Point(int parent) {this.parent = parent;}
}public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int x, y, z, p;Point[] points = new Point[n + 1];for (int i = 1; i < points.length; i++) {points[i] = new Point(i);}ArrayList<int[]> list = new ArrayList<>();HashSet<Integer> set = new HashSet<>();for (int i = 0; i < m; i++) {x = sc.nextInt();y = sc.nextInt();z = sc.nextInt();p = sc.nextInt();set.add(x);set.add(y);if (p == 1) {add(points, x, y, 0);} else {list.add(new int[]{x, y, z});}}Collections.sort(list, Comparator.comparingInt(o -> o[2]));for (int[] ints : list) {add(points, ints[0], ints[1], ints[2]);}int parent = -1;for (int i = 1; i <= n; i++) {if (parent == -1) {parent = getParent(points, i);}if (parent != getParent(points, i)) {System.out.println(-1);return;}}System.out.println(points[parent].cost);}private static void add(Point[] points, int x, int y, int cost) {int parentX = getParent(points, x);int parentY = getParent(points, y);if (parentY == parentX) {return;}if (points[parentY].size <= points[parentX].size) {points[parentY].parent = points[parentX].parent;points[parentX].size += points[parentY].size;points[parentX].cost += cost + points[parentY].cost;} else {points[parentX].parent = points[parentY].parent;points[parentY].size += points[parentX].size;points[parentY].cost += cost + points[parentX].cost;}}public static int getParent(Point[] points, int index) {while (index != points[index].parent) {index = points[index].parent;}return index;}
}

思路:主要就是并查集的思想,不断更新父节点,比较时比较size,哪个集合多哪个就作为父,先排序,按照成本排序,如果已经连接则跳过

相关文章:

华为od-C卷200分题目6 - 5G 网络建设

华为od-C卷200分题目6 - 5G 网络建设 题目描述 现需要在某城市进行 5G 网络建设&#xff0c;已经选取 N 个地点设置 5G 基站&#xff0c;编号固定为 1 到 N&#xff0c;接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通&#xff0c;不同基站之间架设光纤的成本各不…...

步进电机(STM32+28BYJ-48)

一、简介 步进电动机&#xff08;stepping motor&#xff09;把电脉冲信号变换成角位移以控制转子转动的执行机构。在自动控制装置中作为执行器。每输入一个脉冲信号&#xff0c;步进电动机前进一步&#xff0c;故又称脉冲电动机。步进电动机多用于数字式计算机的外部设备&…...

Node.js介绍 , 安装与使用

1.Node.js 1 什么是Node.js 官网&#xff1a;https://nodejs.org/zh-cn/ 中文学习网&#xff1a;http://nodejs.cn/learn1.Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境。Node.js 使用了一个事件驱动、非阻塞式 I/O 的模型,使其轻量又高效。 2.前端的底层 html…...

JavaEE初阶-网络原理1

文章目录 前言一、UDP报头二、UDP校验和2.1 CRC2.2 md5 前言 学习一个网络协议&#xff0c;最主要就是学习的报文格式&#xff0c;对于UDP来说&#xff0c;应用层数据到达UDP之后&#xff0c;会给应用层数据报前面加上UDP报头。 UDP数据报UDP包头载荷 一、UDP报头 如上图UDP的…...

leetcode秋招冲刺 (专题16--18)

专题16&#xff1a;分治 题目169&#xff1a;多数元素&#xff08;YES&#xff09; 解题思路&#xff1a;使用哈希表可以统计出现次数的性质&#xff0c;直接统计就行。 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊…...

学懂C#编程:实用方法——string字符串指定连接符拼接之 string.Join 的详细用法

在C#中&#xff0c;string.Join 方法用于将一个字符串数组或集合中的元素连接成一个单一的字符串&#xff0c;并在每个元素之间插入指定的分隔符。这个方法非常有用&#xff0c;特别是在需要将多个字符串合并成一个字符串时。以下是 string.Join 方法的详细用法&#xff1a; 方…...

Javascript常见数据结构和设计模式

在JavaScript中&#xff0c;常见的数据结构包括两大类&#xff1a;原始数据类型&#xff08;Primitive Types&#xff09;和对象类型&#xff08;Object Types&#xff09;。对象类型又可以进一步细分为多种内置对象、数组、函数等。下面是一些JavaScript中常见的数据结构&…...

【ChatGPT】全面解析 ChatGPT:从起源到未来

ChatGPT 是由 OpenAI 开发的一个基于 GPT&#xff08;Generative Pre-training Transformer&#xff09;架构的聊天机器人。通过自然语言处理&#xff08;NLP&#xff09;技术&#xff0c;ChatGPT 能够理解和生成语言&#xff0c;与人类进行对话。本文将深入探讨其起源、发展、…...

html+css+js贪吃蛇游戏

贪吃蛇游戏&#x1f579;四个按钮控制方向&#x1f3ae; 源代码在图片后面 点赞❤️关注&#x1f64f;收藏⭐️ 互粉必回&#x1f64f;&#x1f64f;&#x1f60d;&#x1f60d;&#x1f60d; 源代码&#x1f4df; <!DOCTYPE html> <html lang"en"&…...

新手必学:掌握Excel中这些常用公式,轻松提升数据处理能力

各位同学好&#xff0c;今天和大家来分享几个常用函数公式的典型用法。 1、提取指定条件的不重复名单 如下图所示&#xff0c;某公司课程比赛&#xff0c;同一员工有多个比赛项目。希望从左侧的列表中&#xff0c;提取出财务部的参赛人员名单。F2单元格输入以下公式&#xff0…...

经济寒冬:竞品凶猛,你的产品如何求生?

那些年曾被竞品干掉的产品 1997年到2010年左右是国内互联网行业的快速发展和多元化发展的时期&#xff0c;这一时期涌现出来一大批优秀的产品&#xff0c;市场竞争越来越激烈。苹果 在20 世纪 80 年代&#xff0c;乔布斯的苹果电脑&#xff0c;在当时可是PC行业的老大&#xf…...

信号量——Linux并发之魂

欢迎来到 破晓的历程的 博客 引言 今天&#xff0c;我们继续学习Linux线程本分&#xff0c;在Linux条件变量中&#xff0c;我们对条件变量的做了详细的说明&#xff0c;今天我们要利用条件变量来引出我们的另一个话题——信号量内容的学习。 1.复习条件变量 在上一期博客中&…...

自动驾驶中的逆透视变换(Inverse Perspective Mapping,IPM)详解

前言 IPM(Inverse Perspective Mapping,逆透视变换)图的历史可以追溯到计算机视觉和图像处理领域的发展。逆透视变换是一种用于消除图像中透视效应的技术,使得原本由于透视产生的形变得以纠正,进而更准确地描述和理解图像中的场景。比如在行车中的车道线检测,泊车中的常见…...

Python地震波逆问题解构算法复杂信号分析

&#x1f3af;要点 &#x1f3af;时域、时频域以及时间和频率相关联偏振特性分析三种算法 | &#x1f3af;时域波参数估计算法 | &#x1f3af;机器学习模型波形指纹分析算法 | &#x1f3af;色散曲线和频率相关波分析算法 | &#x1f3af;动态倾斜校正算法 | &#x1f3af;声…...

C语言 -- 深入理解指针(二)

C语言 -- 深入理解指针&#xff08;二&#xff09; 1. 数组名的理解2. 使用指针访问数组3. 一维数组传参的本质4. 冒泡排序5. 二级指针6. 指针数组7. 指针数组模拟二维数组8. 字符指针变量9. 数组指针变量2.1数组指针变量是什么&#xff1f;2.2 数组指针变量怎么初始化 10. 二维…...

HTTP协议详解

HTTP协议详解 一、HTTP协议概述二、网络基础与HTTP2.1 TCP/IP协议2.2 发送HTTP请求过程2.3 HTTP请求的组成部分 三、HTTP报文HTTP请求报文HTTP响应报文 结语 一、HTTP协议概述 HTTP&#xff0c;即超文本传输协议&#xff08;Hypertext Transfer Protocol&#xff09;&#xff…...

一年时间业绩增长2倍,茅台保健酒业公司在川销售的“三板斧”

执笔 | 尼 奥 编辑 | 扬 灵 作为土地面积全国第5、人口总数全国第3、GDP全国第6的产酒、销酒大省&#xff0c;四川酒类消费总额已达800亿元&#xff0c;其中白酒市场规模达到500亿元。 近年来&#xff0c;随着省外名酒提升对四川市场重视&#xff0c;其市场份额也从20年前的3%…...

土豆炒肉做法

菜单&#xff1a;土豆、葱、铁辣子、纯瘦肉、淀粉、生抽、酱油、刀、案板、十三香、盐巴、擦板 流程&#xff1a; 洗土豆&#xff0c;削皮&#xff0c;擦成条&#xff0c;用凉水过滤两遍淀粉&#xff0c;顺便放个燥里洗肉&#xff0c;切成条&#xff0c;按照生抽、酱油、淀粉、…...

VPS拨号服务器:独享的高效与安全

在当今互联网高速发展的时代&#xff0c;虚拟私人服务器&#xff08;VPS&#xff09;已成为许多企业和个人用户托管网站、应用程序的首选。特别是带有拨号功能的VPS服务器&#xff0c;以其独特的优势受到广泛关注。本文将深入探讨VPS拨号服务器的独享特性&#xff0c;以及它如何…...

网络安全设备——防火墙

网络安全设备防火墙是一种用来加强网络之间访问控制的特殊网络互联设备。以下是对防火墙的详细解释&#xff1a; 一、定义与基本概念 定义&#xff1a;防火墙是指设置在不同网络&#xff08;如可信任的企业内部网和不可信的公共网&#xff09;或网络安全域之间的一系列部件的…...

IPATool终极指南:如何用命令行轻松获取iOS应用安装包?

IPATool终极指南&#xff1a;如何用命令行轻松获取iOS应用安装包&#xff1f; 【免费下载链接】ipatool Command-line tool that allows searching and downloading app packages (known as ipa files) from the iOS App Store 项目地址: https://gitcode.com/GitHub_Trendin…...

Linux内核随机数API

Linux内核为不同需求的场景&#xff08;如密码学安全、高性能模拟、概率采样等&#xff09;提供了多种获取随机数的方式&#xff0c;同时也支持生成概率值&#xff08;例如按一定概率选择分支&#xff09;。下面分类介绍&#xff1a; 一、内核态可用的随机数API 1. 密码学安全的…...

蓝桥杯菜鸟错题

遍历一个字符串内比较&#xff0c;j 应从 i 的后一位开始&#xff0c;保证不重复...

UniApp多商户小程序自动化发布:基于Jenkins与miniprogram-ci的SaaS化部署实践

1. 为什么需要自动化发布多商户小程序&#xff1f; 做过SaaS平台的朋友都知道&#xff0c;当你的平台上有成百上千个商户&#xff0c;每个商户都需要独立的小程序时&#xff0c;手动发布简直就是一场噩梦。我去年接手的一个电商SaaS项目&#xff0c;平台上有300多家商户&#x…...

OpenCascade实战:TopoDS_Shape数据结构的高效遍历与优化策略

1. TopoDS_Shape数据结构基础解析 在OpenCascade中&#xff0c;TopoDS_Shape是构建三维模型的基石。这个看似简单的类实际上包含了三个关键数据成员&#xff1a;myTShape、myLocation和myOrient。理解这三个字段的运作机制&#xff0c;是高效操作模型的前提。 myTShape是一个智…...

Clawdbot 是如何实现永久记忆的?

下文是如何构建的在深入探讨记忆之前&#xff0c;我们先来理解模型在每次请求时能看到什么&#xff1a;[0] 系统提示词&#xff08;静态指令 条件指令&#xff09; [1] 项目上下文&#xff08;引导文件&#xff1a;AGENTS.md、SOUL.md 等&#xff09; [2] 对话历史&#xff08…...

猫抓:网页资源获取工具的技术革新与实战应用

猫抓&#xff1a;网页资源获取工具的技术革新与实战应用 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 在数字化时代&#xff0c;我们每天浏览大量…...

中文大模型实战测评:MiniMax、GLM、Kimi谁更适合你的需求?(附详细对比表)

中文大模型实战测评&#xff1a;MiniMax、GLM、Kimi谁更适合你的需求&#xff1f; 当企业技术团队或个人开发者面临中文大模型选型时&#xff0c;往往陷入"参数崇拜"与"场景适配"的矛盾中。本文基于三个月真实项目测试数据&#xff0c;从工程落地视角拆解三…...

长脉冲激光打孔技术及其与水平集算法的融合应用

长脉冲激光打孔&#xff0c;水平集算法工业级激光打孔就像用光做的"绣花针"&#xff0c;在金属表面精准戳出微米级孔洞。但当我们把激光脉冲时间拉长到毫秒量级时&#xff0c;事情就变得有趣起来——材料不再是瞬间汽化&#xff0c;而是经历缓慢的熔融、流动、再凝固…...

intv_ai_mk11实战手册:构建AI增强型Confluence知识库——自动打标签+关联推荐

intv_ai_mk11实战手册&#xff1a;构建AI增强型Confluence知识库——自动打标签关联推荐 1. 项目背景与价值 在现代企业知识管理中&#xff0c;Confluence作为广泛使用的知识库平台&#xff0c;面临着内容组织效率低下的挑战。传统手动分类和标签管理方式存在三个核心痛点&am…...