页面加载中…
P4500. 5G 网络建设
困难社区常称：5G网络建设
通过率 42% · 提交 175 · 通过 74
200分2024E2024D并查集最小生成树2025C双机位B图论贪心
华为 OD 机考真题方向改编 · 聚焦「200分 / 2024E」 · 难度：困难
小慕正在参与一个 5G 网络建设项目，需要在城市中选取 N 个地点部署 5G 基站，这些基站的编号固定为 1 到 N。接下来，小慕需要将各个基站用光纤连接起来，以确保它们能够互联互通。不同基站之间铺设光纤的成本各不相同，而且有些基站之间已经存在现成的光纤连接。请你帮小慕设计一个算法，计算出连通所有基站所需的最小总成本。 注意，基站的连通具有传递性：如果基站 A 与基站 B 之间铺设了光纤，基站 B 与基站 C 之间也铺设了光纤，那么基站 A 与基站 C 就可以视为互相连通。
这类题属于华为 OD 机考真题方向中「200分 / 2024E」方向的高频题型，通常考察对「200分 / 2024E」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行输入表示基站的个数 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
示例
示例 1
输入示例
3 3 1 2 3 0 1 3 1 0 2 3 5 0
输出示例
4
说明：
只需要在 1,2 以及 2,3 基站之间铺设光纤，其成本为 3+1=4
示例 2
输入示例
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
