华为OD机试统一考试D卷C卷 - 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
用例1
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出
4
说明
只需要在1,2以及1,3基站之间铺设光纤,其成本为3+1=4
用例2
输入
3
1
1 2 5 0
输出
-1
说明
3基站无法与其他基站连接,输出-1
用例3
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 1
输出
1
说明
2,3基站已有光纤相连,只要在1,3基站之间铺设光纤,其成本为1
Java
import java.util.*;
public class Main {
// 并查集数组
static int[] parent;
// 并查集查找函数,用于查找x所在的集合
static int find(int x) {
// 如果x不是自己的父节点,那么就让x的父节点为x的父节点的父节点(路径压缩)
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
// 返回x的父节点
return parent[x];
}
// 定义边的类
static class Edge {
int u, v, cost, pre;
// 构造函数
public Edge(int u, int v, int cost, int pre) {
this.u = u; // 基站u
this.v = v; // 基站v
this.cost = cost; // 架设光纤的成本
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试E卷D卷题 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD(D)卷的题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。