題目描述
現(xiàn)需要在某城市進(jìn)行5G網(wǎng)絡(luò)建設(shè)，已經(jīng)選取N個(gè)地點(diǎn)設(shè)置5G基站，編號(hào)固定為1到N，接下來(lái)需要各個(gè)基站之間使用光纖進(jìn)行連接以確保基站能互聯(lián)互通，不同基站之間假設(shè)光纖的成本各不相同，且有些節(jié)點(diǎn)之間已經(jīng)存在光纖相連。

請(qǐng)你設(shè)計(jì)算法，計(jì)算出能聯(lián)通這些基站的最小成本是多少。

注意：基站的聯(lián)通具有傳遞性，比如基站A與基站B架設(shè)了光纖，基站B與基站C也架設(shè)了光纖，則基站A與基站C視為可以互相聯(lián)通。

輸入描述
第一行輸入表示基站的個(gè)數(shù)N，其中：

0 < N ≤ 20
第二行輸入表示具備光纖直連條件的基站對(duì)的數(shù)目M，其中：

0 < M < N * (N - 1) / 2
從第三行開(kāi)始連續(xù)輸入M行數(shù)據(jù)，格式為

X Y Z P

其中：

X，Y 表示基站的編號(hào)

0 < X ≤ N
0 < Y ≤ N
X ≠ Y
Z 表示在 X、Y之間架設(shè)光纖的成本

0 < Z < 100
P 表示是否已存在光纖連接，0 表示未連接，1表示已連接

輸出描述
如果給定條件，可以建設(shè)成功互聯(lián)互通的5G網(wǎng)絡(luò)，則輸出最小的建設(shè)成本

如果給定條件，無(wú)法建設(shè)成功互聯(lián)互通的5G網(wǎng)絡(luò)，則輸出 -1

用例1
輸入
3
3
1 2 3 0
1 3 1 0
2 3 5 0
輸出
4
說(shuō)明
只需要在1，2以及1，3基站之間鋪設(shè)光纖，其成本為3+1=4

用例2
輸入
3
1
1 2 5 0
輸出
-1
說(shuō)明
3基站無(wú)法與其他基站連接，輸出-1

用例3
輸入
3
3
1 2 3 0
1 3 1 0
2 3 5 1
輸出
1
說(shuō)明
2，3基站已有光纖相連，只要在1，3基站之間鋪設(shè)光纖，其成本為1文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-854673.html

import java.util.*;

// 最小生成樹(shù)
/*其他知識(shí)點(diǎn)：
 在一個(gè)list中修改node數(shù)據(jù)也會(huì)引起另一個(gè)list的node數(shù)據(jù)修改
 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;
        // 初始建設(shè)成本 為 0
        if(M < N-1){
            // 如果 已知可直連的 數(shù)目 M 小于 N-1  則不可能連通
            // 最小生成樹(shù) 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);
                    //已鏈接線路的長(zhǎng)度 置 0
                    nodeList.add(node);
                }
                // 這里沒(méi)有拋出異常 默認(rèn) 給定的數(shù)據(jù)就是數(shù)字的字符串了
            } else {
                System.out.println(-1);
                return;
            }
            // data.add(tempString);
            // System.out.println(tempString);
        }

        // 運(yùn)行到這里 已經(jīng)默認(rèn) M >= N - 1
        // 需要求出最小生成樹(shù)
        // 給list排序
        nodeList.sort(new Comparator<Node>(){
            @Override
            public int compare(Node node1,Node node2){
                return node1.z-node2.z;
                // 此時(shí) 按照 z 遞增序列 重排list
            } 
        });
        //測(cè)試nodelist是否正確
        /*for (Node node : nodeList) {
            System.out.println(node.x + " " + node.y + " " + node.z + " " + node.p);
        }*/

        UnionFind unionFind = new UnionFind(N+1);
        // 0 號(hào)空缺不用  從 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 號(hào)元素 沒(méi)有到 故當(dāng)連通分量為 2 的時(shí)候 有效連通分量只有 1個(gè) 
                    // 最小生成樹(shù)構(gòu)造完成
                    break;
                }
            }
        }
        if(unionFind.getCount()==2){
            // 若沒(méi)有形成 最小生成樹(shù) 也會(huì)最終從循環(huán)中出來(lái) 要判斷是否形成了最小生成樹(shù)
             System.out.print(sum);
        }
        else{
            System.out.print(-1);
        }
    }
}


class UnionFind{
    // 并查集 N個(gè)元素
    private int n;

    private int[] parent;
    //父指針數(shù)組

    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;
            // 初始時(shí) 父指針指向自己
        }

        this.count = n;
        // 初始時(shí) 連通分量個(gè)數(shù)等于 元素個(gè)數(shù)
    }

    public void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ){
            // 已經(jīng)位于同一個(gè)連通分量之中
            return;
        }
        else{
            // union操作
            parent[rootP] = rootQ;
            // rootP 的父指針指向 rootQ
            this.count--;
            // 連通分量個(gè)數(shù)減一
        }
    }

    public int find(int element){
        // 找根節(jié)點(diǎn)
        if(parent[element] != element){// 當(dāng) element自己不是根節(jié)點(diǎn)的時(shí)候  
            // 遞歸函數(shù)
            parent[element] = find(parent[element]);
            // find 找 element 的上層節(jié)點(diǎn)的上層節(jié)點(diǎn)
            // 以此類(lèi)推
            // 當(dāng)找到根節(jié)點(diǎn)root 的時(shí)候parent[次節(jié)點(diǎn)] = find(parent[次節(jié)點(diǎn)]) = find(root) = root
            // parent[次次節(jié)點(diǎn)] = find(parent[次次節(jié)點(diǎn)]) = find(次節(jié)點(diǎn))
            // 由于 次節(jié)點(diǎn)!=parent[次節(jié)點(diǎn)] 則parent[次次節(jié)點(diǎn)] = find(次節(jié)點(diǎn)) = parent[次節(jié)點(diǎn)] = root
            // 以此類(lèi)推

            // 則將 實(shí)際樹(shù)高設(shè)置為 2  根節(jié)點(diǎn)root直接與所有子節(jié)點(diǎn)相連
        } 
        return parent[element];
    }

    public boolean connected(int p, int q){
        // 判斷 p q 是否在同一個(gè)連通分量當(dāng)中
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    public int getCount(){
        // 返回連通分量個(gè)數(shù)
        return this.count;
    }
}

到了這里，關(guān)于5G網(wǎng)絡(luò)建設(shè)--并查集--最小生成樹(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！