5G 网络建设【华为OD机试-JAVAPythonC++JS】

题目描述

现需要在某城市进行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以及2,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

解题思路

这个问题可以使用最小生成树（Minimum Spanning Tree）的思想来解决，Kruskal算法是一种常用的实现方式。下面是解题思路：

将所有基站之间的光纤连接按照成本从小到大排序，初始化一个并查集（Union-Find）用于记录基站的联通情况。
遍历排序后的光纤连接，逐个连接基站，如果连接后不形成环（即两个基站不在同一个集合中），则将它们合并，累加连接的成本。
当联通的基站数量达到N-1时，即所有基站都联通，停止连接。
如果最终联通的基站数量不等于N-1，说明无法建设成功互联互通的5G网络，输出-1；否则输出累加的连接成本。

题解代码

Python题解代码

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        cities = len(isConnected)
        visited = set()
        provinces = 0
        
        for i in range(cities):
            if i not in visited:
                Q = collections.deque([i])
                while Q:
                    j = Q.popleft()
                    visited.add(j)
                    for k in range(cities):
                        if isConnected[j][k] == 1 and k not in visited:
                            Q.append(k)
                provinces += 1
        
        return provinces

JAVA题解代码



class Solution {
    public int findCircleNum(int[][] isConnected) {
        int ans = 0, n = isConnected.length;
        boolean[] visit = new boolean[n];
        for(int i = 0; i < n; ++i){
            if(!visit[i]){
                ans++;
                bfs(i, visit, isConnected);
            }
        }
        return ans;
    }
    public void bfs(int i, boolean[] visit, int[][] isConnected){
        for(int j = 0; j < isConnected.length; ++j){
            if(isConnected[i][j] == 1 && !visit[j]){
                visit[j] = true;
                bfs(j, visit, isConnected);
            }
        }
    }
}

C/C++题解代码

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int cities = isConnected.size();
        vector<int> visited(cities);
        int provinces = 0;
        queue<int> Q;
        for (int i = 0; i < cities; i++) {
            if (!visited[i]) {
                Q.push(i);
                while (!Q.empty()) {
                    int j = Q.front(); Q.pop();
                    visited[j] = 1;
                    for (int k = 0; k < cities; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            Q.push(k);
                        }
                    }
                }
                provinces++;
            }
        }
        return provinces;
    }
};

JS题解代码


var findCircleNum = function(isConnected) {
    const cities = isConnected.length;
    const visited = new Set();
    let provinces = 0;
    const queue = new Array();
    for (let i = 0; i < cities; i++) {
        if (!visited.has(i)) {
            queue.push(i);
            while (queue.length) {
                const j = queue.shift();
                visited.add(j);
                for (let k = 0; k < cities; k++) {
                    if (isConnected[j][k] === 1 && !visited.has(k)) {
                        queue.push(k);
                    }
                }
            }
            provinces++;
        }
    }
    return provinces;
};