华为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,哪个集合多哪个就作为父,先排序,按照成本排序,如果已经连接则跳过