华为OD机试真题 - 5G网络建设

并查集+Kruskal 算法 解决

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = Integer.parseInt(in.nextLine());
        int n = Integer.parseInt(in.nextLine());
        Map[] maps = new Map[n];
        for (int i = 0; i < n; i++) {
            int[] map =  Arrays.stream(in.nextLine().split(&quot; &quot;)).mapToInt(Integer::parseInt).toArray();
            maps[i] = new Map(map[0], map[1], map[2], map[3] == 1);
        }
        Arrays.sort(maps, new Comparator<Map>() {
            @Override
            public int compare(Map o1, Map o2) {
                if (o1.has)
                    return -1;
                if (o2.has)
                    return 1;
                return o1.cost - o2.cost;
            }
        });

        UnionFindSet unionFindSet = new UnionFindSet(num);
        int cost = 0;
        for (int i = 0; i < maps.length; i++) {
            if (maps[i].has) {
                unionFindSet.union(maps[i].x - 1, maps[i].y - 1);
                continue;
            }
            if (unionFindSet.find(maps[i].x - 1) != unionFindSet.find(maps[i].y - 1)) {
                unionFindSet.union(maps[i].x - 1, maps[i].y - 1);
                cost += maps[i].cost;
            }
        }
        System.out.println(cost);
    }

    static class Map {
        public int x;
        public int y;
        public int cost;
        public boolean has = false;

        public Map(int x, int y, int cost, boolean has) {
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.has = has;
        }
    }

    static class UnionFindSet {
        int[] parent = null;

        public UnionFindSet(int count) {
            this.parent = new int[count];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] == x)
                return x;
            else return parent[x] = find(parent[x]);
        }

        public void union(int i , int j) {
            int f_i = find(i);
            int f_j = find(j);
            if (f_i != f_j) {
                for (int k = 0; k < parent.length; k++) {
                    if (parent[k] == f_j)
                        parent[k] = f_i;
                }
            }
        }
    }