5G网络建设--并查集--最小生成树-Toy模板网

这篇具有很好参考价值的文章主要介绍了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 < 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文章来源地址https://www.toymoban.com/news/detail-854673.html

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;
        // 初始建设成本 为 0
        if(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);
                    //已链接线路的长度 置 0
                    nodeList.add(node);
                }
                // 这里没有抛出异常 默认 给定的数据就是数字的字符串了
            } else {
                System.out.println(-1);
                return;
            }
            // data.add(tempString);
            // System.out.println(tempString);
        }

        // 运行到这里 已经默认 M >= N - 1
        // 需要求出最小生成树
        // 给list排序
        nodeList.sort(new Comparator<Node>(){
            @Override
            public 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 - N

        for(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 的父指针指向 rootQ
            this.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;
    }
}