怎么用 做网站,莆田网站制作,品牌建设方式有哪些,安平县哪里做网站华为od-C卷200分题目6 - 5G 网络建设
题目描述 现需要在某城市进行 5G 网络建设#xff0c;已经选取 N 个地点设置 5G 基站#xff0c;编号固定为 1 到 N#xff0c;接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通#xff0c;不同基站之间架设光纤的成本各不…华为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 100P 表示是否已存在光纤连接0 表示未连接 1 表示已连接。
输出 如果给定条件可以建设成功互联互通的 5G 网络则输出最小的建设成本
如果给定条件无法建设成功互联互通的 5G 网络则输出-1
样例输入 复制 3 3 1 2 3 0 1 3 1 0 2 3 5 0 样例输出 复制 4 提示 只需要在 1,2 以及 2,3 基站之间铺设光纤其成本为 314
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);}ArrayListint[] list new ArrayList();HashSetInteger 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哪个集合多哪个就作为父先排序按照成本排序如果已经连接则跳过
