题目描述
现需要在某城市进行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

用例1
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出
4
说明
只需要在1，2以及1，3基站之间铺设光纤，其成本为3+1=4

用例2
输入
3
1
1 2 5 0
输出
-1
说明
3基站无法与其他基站连接，输出-1

用例3
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 1
输出
1
说明
2，3基站已有光纤相连，只要在1，3基站之间铺设光纤，其成本为1

import java.util.*;// 最小生成树
/*其他知识点：在一个list中修改node数据也会引起另一个list的node数据修改list中存放的是node的地址引用
*/
class Node {// 这里用node表示直连线路public int x;public int y;public int z;public boolean p;public Node(int x, int y, int z, boolean p) {this.x = x;this.y = y;this.z = z;this.p = p;}public Node(Node other){this.x = other.x;this.y = other.y;this.z = other.z;this.p = other.p;}
}public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int N = in.nextInt();int M = in.nextInt();int sum = 0;// 初始建设成本 为 0if(M < N-1){// 如果 已知可直连的 数目 M 小于 N-1  则不可能连通// 最小生成树 N-1 条边 保证连通System.out.println(-1);return;}String temp = in.nextLine();// ArrayList<String> data = new ArrayList<String>();ArrayList<Node> nodeList = new ArrayList<Node>();// 全部线路while (M>0) {// 输入M行M--;String tempString = in.nextLine();//System.out.println("tempString: " + tempString);String[] charString = tempString.split(" ");if (charString.length == 4) {if(charString[3].equals("0")){Node node = new Node(Integer.valueOf(charString[0]).intValue(),Integer.valueOf(charString[1]).intValue(),Integer.valueOf(charString[2]).intValue(),false);                nodeList.add(node);}else{Node node = new Node(Integer.valueOf(charString[0]).intValue(),Integer.valueOf(charString[1]).intValue(),0,true);//已链接线路的长度 置 0nodeList.add(node);}// 这里没有抛出异常 默认 给定的数据就是数字的字符串了} else {System.out.println(-1);return;}// data.add(tempString);// System.out.println(tempString);}// 运行到这里 已经默认 M >= N - 1// 需要求出最小生成树// 给list排序nodeList.sort(new Comparator<Node>(){@Overridepublic int compare(Node node1,Node node2){return node1.z-node2.z;// 此时 按照 z 递增序列 重排list} });//测试nodelist是否正确/*for (Node node : nodeList) {System.out.println(node.x + " " + node.y + " " + node.z + " " + node.p);}*/UnionFind unionFind = new UnionFind(N+1);// 0 号空缺不用  从 1 - Nfor(Node node:nodeList){if(!unionFind.connected(node.x,node.y)){unionFind.union(node.x,node.y);sum+=node.z;if(unionFind.getCount() == 2){// 0 号元素 没有到 故当连通分量为 2 的时候 有效连通分量只有 1个 // 最小生成树构造完成break;}}}if(unionFind.getCount()==2){// 若没有形成 最小生成树 也会最终从循环中出来 要判断是否形成了最小生成树System.out.print(sum);}else{System.out.print(-1);}}
}class UnionFind{// 并查集 N个元素private int n;private int[] parent;//父指针数组private int count;public UnionFind(int n){this.n = n;this.parent = new int[n];for(int i=0;i<n;i++){parent[i] = i;// 初始时 父指针指向自己}this.count = n;// 初始时 连通分量个数等于 元素个数}public void union(int p, int q){int rootP = find(p);int rootQ = find(q);if(rootP == rootQ){// 已经位于同一个连通分量之中return;}else{// union操作parent[rootP] = rootQ;// rootP 的父指针指向 rootQthis.count--;// 连通分量个数减一}}public int find(int element){// 找根节点if(parent[element] != element){// 当 element自己不是根节点的时候  // 递归函数parent[element] = find(parent[element]);// find 找 element 的上层节点的上层节点// 以此类推// 当找到根节点root 的时候parent[次节点] = find(parent[次节点]) = find(root) = root// parent[次次节点] = find(parent[次次节点]) = find(次节点)// 由于 次节点!=parent[次节点] 则parent[次次节点] = find(次节点) = parent[次节点] = root// 以此类推// 则将 实际树高设置为 2  根节点root直接与所有子节点相连} return parent[element];}public boolean connected(int p, int q){// 判断 p q 是否在同一个连通分量当中int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}public int getCount(){// 返回连通分量个数return this.count;}
}