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

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 5G基站光纤连接问题(200分) - 三语言AC题解(Python/Java/Cpp)

🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1072

🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁~

🍓OJ题目截图

在这里插入图片描述

文章目录

    • 📎在线评测链接
    • 🍓OJ题目截图
    • 🍿 5G基站光纤连接问题
      • 问题描述
      • 输入格式
      • 输出格式
      • 样例输入
        • 样例 1
        • 样例 2
        • 样例 3
      • 样例输出
        • 样例 1 输出
        • 样例 2 输出
        • 样例 3 输出
      • 样例解释
        • 样例 1 解释
        • 样例 2 解释
        • 样例 3 解释
      • 数据范围
      • 题解
      • 参考代码

🍿 5G基站光纤连接问题

问题描述

K小姐是一家通信公司的网络工程师,她最近被分配了一项任务:在某个城市建设5G网络。该城市已经选定了 n n n 个地点作为5G基站的位置,编号从 1 1 1 n n n。为了确保所有基站能够互联互通,K小姐需要在这些基站之间架设光纤进行连接。不同基站之间架设光纤的成本各不相同,而且有些基站之间已经存在光纤相连。K小姐的任务是设计一个算法,计算出能够联通所有基站的最小成本。需要注意的是,基站的联通具有传递性,即如果基站 A A A 与基站 B B B 架设了光纤,基站 B B B 与基站 C C C 也架设了光纤,那么基站 A A A 与基站 C C C 也视为可以互相联通。

输入格式

第一行输入一个正整数 n n n,表示基站的个数,其中 0 < n ≤ 20 0 < n \leq 20 0<n20

第二行输入一个正整数 m m m,表示具备光纤直连条件的基站对的数目,其中 0 < m < n ( n − 1 ) 2 0 < m < \frac{n(n-1)}{2} 0<m<2n(n1)

从第三行开始连续输入 m m m 行数据,每行的格式为 x y z p x\ y\ z\ p x y z p,其中 x x x y y y 表示基站的编号,满足 0 < x ≤ n 0 < x \leq n 0<xn 0 < y ≤ n 0 < y \leq n 0<yn x ≠ y x \neq y x=y; z z z 表示在 x x x y y y 之间架设光纤的成本,满足 0 < z < 100 0 < z < 100 0<z<100; p p p 表示是否已存在光纤连接,取值为 0 0 0 1 1 1,其中 0 0 0 表示未连接,而 1 1 1 表示已连接。

输出格式

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

样例输入

样例 1
3
3
1 2 3 0
1 3 1 0
2 3 5 0
样例 2
3
1
1 2 5 0
样例 3
3
3
1 2 3 0
1 3 1 0
2 3 5 1

样例输出

样例 1 输出
4
样例 2 输出
-1
样例 3 输出
1

样例解释

样例 1 解释

只需要在基站 1 1 1 和基站 2 2 2 之间,以及基站 2 2 2 和基站 3 3 3 之间铺设光纤,其成本为 3 + 1 = 4 3 + 1 = 4 3+1=4

样例 2 解释

基站 3 3 3 无法与其他基站连接,因此无法建设成功互联互通的5G网络,输出 − 1 -1 1

样例 3 解释

基站 2 2 2 和基站 3 3 3 已有光纤相连,只需要在基站 1 1 1 和基站 3 3 3 之间铺设光纤,其成本为 1 1 1

数据范围

  • 0 < n ≤ 20 0 < n \leq 20 0<n20
  • 0 < m < n ( n − 1 ) 2 0 < m < \frac{n(n-1)}{2} 0<m<2n(n1)
  • 0 < x , y ≤ n 0 < x, y \leq n 0<x,yn, x ≠ y x \neq y x=y
  • 0 < z < 100 0 < z < 100 0<z<100
  • p ∈ { 0 , 1 } p \in \{0, 1\} p{0,1}

题解

这是一个经典的最小生成树问题,可以使用 Kruskal 算法或 Prim 算法求解。这里我们采用 Kruskal 来解决,首先将所有已经存在光纤连接的基站对进行合并,然后按照架设光纤的成本从小到大排序,依次尝试连接未连通的基站对。如果连接后不会形成环路,则将该条边加入最小生成树中。当所有基站都被连通后,最小生成树的边权之和就是最小的建设成本。

如果最终无法将所有基站连通,则输出 − 1 -1 1

参考代码

  • Python
# 并查集
class UnionFind:def __init__(self, n):self.parent = list(range(n + 1))self.rank = [0] * (n + 1)def find(self, x):if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])return self.parent[x]def union(self, x, y):px, py = self.find(x), self.find(y)if px == py:returnif self.rank[px] < self.rank[py]:self.parent[px] = pyelif self.rank[px] > self.rank[py]:self.parent[py] = pxelse:self.parent[py] = pxself.rank[px] += 1n = int(input())
m = int(input())
uf = UnionFind(n)
edges = []for _ in range(m):x, y, w, p = map(int, input().split())if p == 1:uf.union(x, y)else:edges.append((w, x, y))edges.sort()
cost = 0
for w, x, y in edges:if uf.find(x) != uf.find(y):uf.union(x, y)cost += wif len(set(uf.find(i) for i in range(1, n + 1))) == 1:print(cost)
else:print(-1)
  • Java
import java.util.*;class UnionFind {int[] parent;int[] rank;public UnionFind(int n) {parent = new int[n + 1];rank = new int[n + 1];for (int i = 0; i <= n; i++) {parent[i] = i;}}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}public void union(int x, int y) {int px = find(x);int py = find(y);if (px == py) {return;}if (rank[px] < rank[py]) {parent[px] = py;} else if (rank[px] > rank[py]) {parent[py] = px;} else {parent[py] = px;rank[px]++;}}
}public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();UnionFind uf = new UnionFind(n);List<int[]> edges = new ArrayList<>();for (int i = 0; i < m; i++) {int x = sc.nextInt();int y = sc.nextInt();int w = sc.nextInt();int p = sc.nextInt();if (p == 1) {uf.union(x, y);} else {edges.add(new int[]{w, x, y});}}edges.sort((a, b) -> a[0] - b[0]);int cost = 0;for (int[] edge : edges) {int w = edge[0];int x = edge[1];int y = edge[2];if (uf.find(x) != uf.find(y)) {uf.union(x, y);cost += w;}}Set<Integer> roots = new HashSet<>();for (int i = 1; i <= n; i++) {roots.add(uf.find(i));}if (roots.size() == 1) {System.out.println(cost);} else {System.out.println(-1);}}
}
  • Cpp
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class UnionFind {
private:vector<int> parent;vector<int> rank;public:UnionFind(int n) {parent.resize(n + 1);rank.resize(n + 1, 0);for (int i = 0; i <= n; i++) {parent[i] = i;}}int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}void merge(int x, int y) {int px = find(x);int py = find(y);if (px == py) {return;}if (rank[px] < rank[py]) {parent[px] = py;} else if (rank[px] > rank[py]) {parent[py] = px;} else {parent[py] = px;rank[px]++;}}
};int main() {int n, m;cin >> n >> m;UnionFind uf(n);vector<vector<int>> edges;for (int i = 0; i < m; i++) {int x, y, w, p;cin >> x >> y >> w >> p;if (p == 1) {uf.merge(x, y);} else {edges.push_back({w, x, y});}}sort(edges.begin(), edges.end());int cost = 0;for (auto edge : edges) {int w = edge[0];int x = edge[1];int y = edge[2];if (uf.find(x) != uf.find(y)) {uf.merge(x, y);cost += w;}}bool success = true;int root = uf.find(1);for (int i = 2; i <= n; i++) {if (uf.find(i) != root) {success = false;break;}}if (success) {cout << cost << endl;} else {cout << -1 << endl;}return 0;
}

相关文章:

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 5G基站光纤连接问题(200分) - 三语言AC题解(Python/Java/Cpp)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; &#x1f…...

分层Agent

分层Teams 分层Agent创建tool研究团队工具文档编写团队工具 通用能力定义Agent团队研究团队文档编写团队 添加图层 分层Agent 在前面的示例&#xff08;Agent管理&#xff09;中&#xff0c;我们引入了单个管理节点的概念&#xff0c;用于在不同工作节点之间路由工作。 但是&a…...

OS复习笔记ch11-1

外围设备的管理和磁盘调度 外围设备 从CPU的角度来看&#xff0c;外设有几个比较重要的I/O接口&#xff08;interfaces&#xff09; 状态reg&#xff1a;向CPU报告设备的状态&#xff08;忙碌/空闲&#xff09;命令reg&#xff1a;接收CPU命令&#xff0c;存储 CPU 需要执行的…...

Docker Compose 使用

一、简介 Docker Compose 是一个工具&#xff0c;用于定义和运行多容器 Docker 应用程序。它允许用户使用 YAML 文件来配置应用程序需要的所有服务&#xff0c;然后使用一个命令来从 YAML 文件配置中创建并启动所有服务。其主要目的是为了简化了多容器 Docker 应用程序的部署和…...

KEIL5.39 5.40 fromelf 不能生成HEX bug

使用AC6 编译,只要勾选了生成HEX。 结果报如下错误 暂时没有好的解决办法 1.替换法 2.在编译完后用命令生成HEX...

mongosh 和mongo 命令行连接MongoDB

Mongoshell MongoDB的Shell工具mongosh是一个全功能的JavaScript和Node.js的14.x REPL与MongoDB的部署交互环境。我们通过它可以直接对数据库进行查询和操作。这个工具是需要在安装玩MongoDB后单独安装的。 与传统的mongo方式连接MongoDB更加丰富。 官网 https://www.mongodb.…...

DOM 改变节点

DOM 改变节点 文档对象模型&#xff08;DOM&#xff09;是 HTML 和 XML 文档的编程接口。它提供了对文档的结构化表示&#xff0c;并定义了一种方式&#xff0c;允许程序和脚本动态地访问和更新文档的内容、结构和样式。在网页开发中&#xff0c;DOM 操作是核心技能之一&#…...

【面试题分享】重现 string.h 库常用的函数

文章目录 【面试题分享】重现 string.h 库常用的函数一、字符串复制1. strcpy&#xff08;复制字符串直到遇到 null 终止符&#xff09;2. strncpy&#xff08;复制固定长度的字符串&#xff09; 二、字符串连接1. strcat&#xff08;将一个字符串连接到另一个字符串的末尾&…...

6.21 移动语义与智能指针

//先构造&#xff0c;再拷贝构造//利用"hello"这个字符串创建了一个临时对象//并复制给了s3//这一步实际上new了两次String s3 "hello"; 背景需求&#xff1a; 这个隐式创建的字符串出了该行就直接销毁掉&#xff0c;效率比较低 可以让_pstr指向这个空间…...

Kimi还能对学术论文进行润色?我来教你!

学境思源&#xff0c;一键生成论文初稿&#xff1a; AcademicIdeas - 学境思源AI论文写作 一、引言 在学术界&#xff0c;论文的质量往往决定了研究的可信度和影响力。Kimi作为一款人工智能助手&#xff0c;可以为学术论文的润色提供有效的帮助。本文将详细介绍如何利用Kimi进…...

智汇云舟成为中煤集团中煤智能创新联盟成员单位

6月21日&#xff0c;第八届世界智能产业博览会平行会议暨中煤智能创新联盟交流会在天津水游城丽筠酒店顺利举行。智汇云舟受邀参与&#xff0c;并由中国中煤能源集团授予荣誉证书&#xff0c;正式成为中煤智能创新联盟成员单位。会议上&#xff0c;清华大学、中国矿业大学&…...

【文心智能体大赛】迎接属于你的休闲娱乐导师!

迎接属于你的休闲娱乐导师&#xff01; 前言创建智能体发布智能体最后结语 前言 文心智能体平台AgentBuilder 是百度推出的基于文心大模型的智能体&#xff08;Agent&#xff09;平台&#xff0c;支持广大开发者根据自身行业领域、应用场景&#xff0c;选取不同类型的开发方式&…...

AI:音乐创作的未来还是毁灭的序曲?

AI&#xff1a;音乐创作的未来还是毁灭的序曲&#xff1f; 随着人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;它已经渗透到了我们生活的方方面面&#xff0c;包括音乐领域。然而&#xff0c;AI在音乐创作中的角色引发了广泛的讨论和争议。一些人认为AI为音乐…...

如何通过AI进行智能日志异常检测

智能日志异常检测是一种利用人工智能&#xff08;AI&#xff09;技术来自动识别日志数据中异常模式或行为的方法。传统日志监控依赖于预定义规则&#xff0c;而智能日志异常检测可以适应不同的日志模式和异常类型&#xff0c;提高检测准确性和效率。下面是一个完整的步骤指南&a…...

C++ GPU编程(英伟达CUDA)

安装编译环境 https://developer.download.nvidia.com/compute/cuda/12.5.0/local_installers/cuda_12.5.0_555.85_windows.exe CMakeLists.txt cmake_minimum_required(VERSION 3.10)set(CMAKE_CXX_STANDARD 17) set(CMAKE_BUILD_TYPE Release) #set(CMAKE_CUDA_ARCHITECTUR…...

肾虚学习实验第T1周:实现mnist手写数字识别

>- **&#x1f368; 本文为[&#x1f517;365天深度学习训练营](https://mp.weixin.qq.com/s/0dvHCaOoFnW8SCp3JpzKxg) 中的学习记录博客** >- **&#x1f356; 原作者&#xff1a;[K同学啊](https://mtyjkh.blog.csdn.net/)** 目录 一、前言 作为一名研究牲&#xff0…...

Python | Leetcode Python题解之第162题寻找峰值

题目&#xff1a; 题解&#xff1a; class Solution:def findPeakElement(self, nums: List[int]) -> int:n len(nums)# 辅助函数&#xff0c;输入下标 i&#xff0c;返回 nums[i] 的值# 方便处理 nums[-1] 以及 nums[n] 的边界情况def get(i: int) -> int:if i -1 or…...

定个小目标之刷LeetCode热题(26)

这道题属于一道简单题&#xff0c;可以使用辅助栈法&#xff0c;代码如下所示 class Solution {public boolean isValid(String s) {if (s.isEmpty())return false;// 创建字符栈Stack<Character> stack new Stack<Character>();// 遍历字符串数组for (char c : …...

网络爬虫设置代理服务器

目录 1&#xff0e;获取代理 IP 2&#xff0e;设置代理 IP 3. 检测代理 IP 的有效性 4. 处理异常 如果希望在网络爬虫程序中使用代理服务器&#xff0c;就需要为网络爬虫程序设置代理服务器。 设置代理服务器一般分为获取代理 IP 、设置代理 IP 两步。接下来&#xff0c;分…...

3、matlab单目相机标定原理、流程及实验

1、单目相机标定流程及步骤 单目相机标定是通过确定相机的内部和外部参数&#xff0c;以便准确地在图像空间和物体空间之间建立映射关系。下面是单目相机标定的流程及步骤&#xff1a; 搜集标定图像&#xff1a;使用不同角度、距离和姿态拍摄一组标定图像&#xff0c;并确保标…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...