[华为OD] C卷 5G网络现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站 200

题目

现需要在某城市进行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 < = ?，0

< Y < = N且X不等于丫，Z表示在X Y之间架设光纤的成本，其中0 < Z < 1 0 0 , P表示是否

已存在光纤连接，0表示未连接，1表示已连接。

输出描述

如果给定条件，可以建设成功互联互通的5G网络，则输出最小的建设成本，

如果给定条件，无法建设成功互联互通的5G网络，则输出-1

示例1：

输入

1 2 3 0

1 3 1 0

2 3 5 0

输出

说明

只需要在1,2以及2,3基站之间铺设光纤，其成本为3+1=4

示例2

输入

1 2 5 0

输出

-1

说明

3基站无法与其他基站连接，输出-1

示例3：

输入

1 2 3 0

1 3 1 0

2 3 5 1

输出

说明

2,3基站已有光纤相连，只有要再1,3站点2向铺设，其成本为1

题解：

这种图节点的题目，优先考虑用并查集的思路进行解决。

关于并查集，可以参考：. - 力扣（LeetCode）

图论——并查集(详细版)_哔哩哔哩_bilibili

带权并查集_哔哩哔哩_bilibili

这三个视频看下大致就清楚并查集和带权并查集了。

并查集主要有三点，查找相同根find(x)，就可以判断是否在同一组网络里面了

联合union(int num1,int num2) ,不同网络里面的num1和num2相连。

这个题目里面还要算最小的联通网络成本，所以我们要构建一个网络，这个数据里面先按照联通成本进行排序，然后轮询，计算两个节点是否在同一个网络，在的话，就不管，不在的话，那么成本就加上，然后并查集中两个节点进行连接。这个题还是比较有难度的

代码：

public class NetNode {
    private int root[];
    private int count;

    public NetNode(int size) {
        root = new int[size+1]; //这里点的序号是从1开始的，所以size要+1
        count = 0;
        for(int i =0;i<size+1;i++){
            root[i] = i;
        }
    }

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

    public void union(int num1,int num2){
        root[find(num1)] = find(num2);
        count++;
    }

    public int getCount(){
        return count;
    }
}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class FiveG {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int totalCount = Integer.valueOf(sc.nextLine());
        int m = Integer.valueOf(sc.nextLine());
        NetNode ne = new NetNode(totalCount);
        List<int[]> netWork = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            String inputStr = sc.nextLine();
            String[] inputArr = inputStr.split(" ");
            int[] inputNum = new int[inputArr.length];
            for (int j = 0; j < inputArr.length; j++) {
                inputNum[j] = Integer.valueOf(inputArr[j]);
            }
            if (inputNum[3] == 1) {
                if (ne.find(inputNum[0]) != ne.find(inputNum[1])) {
                    ne.union(inputNum[0], inputNum[1]);
                }
            } else {
                netWork.add(new int[]{inputNum[0], inputNum[1], inputNum[2]});
            }
        }

        netWork.sort(new Comparator<int[]>() {  //构建成本排序
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        int result = 0;
        for (int i = 0; i < netWork.size(); i++) {
            System.out.println("i=" + i + " netWork.get(i)[0] = " + netWork.get(i)[0] +
                    " netWork.get(i)[1]= " + netWork.get(i)[1]);

            if (ne.find(netWork.get(i)[0]) != ne.find(netWork.get(i)[1])) {
                ne.union(netWork.get(i)[0], netWork.get(i)[1]);
                result += netWork.get(i)[2];
            }

            if(ne.getCount() == totalCount - 1){
                break;
            }
        }

        System.out.println("totalCount = " + ne.getCount());

        if (ne.getCount() < totalCount - 1) {
            System.out.println(-1);
            return;
        }

        System.out.println(result);
    }
}

验证：