OJ-5G网络建设

 示例1

输入：
3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出：
4

示例2

输入：
3
1
1 2 5 0
输出：
-1

示例3

输入：
3
3
1 2 3 0
1 3 1 0
2 3 5 1
输出：
1

分析：压缩路径

顺序：1 2；1 3；2 3；3 4

root[i]	初始化	合并1 2	合并1 3	合并2 3	合并3 4	最终root
root[1]	1	2				4
root[2]	2		3			4
root[3]	3				4	4
root[4]	4					4

顺序：2 3；1 2；1 3；3 4

root[i]	初始化	合并2 3	合并1 2	合并1 3	合并3 4	最终root
root[1]	1		3			4
root[2]	2	3				4
root[3]	3				4	4
root[4]	4					4

结论：优先按照边的权重小的连接，上述4个节点至少需要3条边连接，1 2,1 3,2 3中只需其中任意两条边即能将1、2、3节点连接。

代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class 五G网络建设2 {private static int[] root;private static final List<int[]> edge = new ArrayList<>();public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();root = new int[n + 1];for (int i = 1; i <= n; i++) {root[i] = i;}for (int i = 0; i < m; i++) {int x = in.nextInt();int y = in.nextInt();int z = in.nextInt();int p = in.nextInt();if (p == 1) {merge(x, y);} else {edge.add(new int[]{x, y, z});}}edge.sort((o1, o2) -> o1[2] - o2[2]);int price = 0;for (int[] e : edge) {if (merge(e[0], e[1]) == 1) {price += e[2];}}boolean ok = true;for (int i = 1; i <= n; i++) {if (getRoot(i) != getRoot(1)) {ok = false;break;}}if (ok) {System.out.println(price);} else {System.out.println(-1);}}private static int merge(int x, int y) {int rootX = getRoot(x);int rootY = getRoot(y);if (rootX == rootY) {return 0;}root[rootX] = rootY;return 1;}private static int getRoot(int x) {if (root[x] == x) {return x;}return getRoot(root[x]);}
}

251.【华为OD机试】5G网络建设（最小生成树算法-Java&Python&C++&JS实现）_java算法5g基站-CSDN博客