华为OD机试真题 - 最大矩阵和

并查集+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(" ")).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;                }            }        }    }