首页 > 编程语言 >5G网络建设【华为OD机试】(JAVA&Python&C++&JS题解)

5G网络建设【华为OD机试】(JAVA&Python&C++&JS题解)

时间：2024-04-07 12:31:29浏览次数：26  
标签：JAVA Python 题解 find networks int 基站 uf 节点

一. 题目-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以及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

二.解题思路

这个问题可以通过最小生成树算法来解决，其中最常用的算法之一是Kruskal算法。以下是解题思路：

  1. 初始化一个并查集（Union-Find）用于维护基站之间的连接关系，初始时每个基站都是一个独立的集合。

  2. 将已有的光纤连接（已存在光纤连接的）加入并查集，表示它们已经联通。

  3. 对未连接的基站对按照光纤成本进行升序排序。

  4. 依次遍历排序后的基站对，如果两个基站不在同一集合中，则将它们连接，并将连接的成本累加到结果中。

  5. 继续遍历直到所有基站都联通或者所有可能的连接都尝试完毕。

  6. 如果最终连接的基站数量等于总基站数量减一，则说明成功建设互联互通的5G网络，输出累计的最小成本；否则，输出-1。

这种方法通过贪心地选择成本最小的连接，确保了最终建设的网络成本最小。

三.题解代码

Python题解代码

class UF:
    def __init__(self, size):
        self.root = [i for i in range(size+1)]
        self.rank = [1] * (size+1)
        self.count = 0
 
    def find(self, x):
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
 
    def union(self, x, y):
        self.root[self.find(x)] = self.find(y)
        self.count += 1
 
    def get_count(self):
        return self.count
 
 
if __name__ == "__main__":
    n, m = map(int, input().split())
    uf = UF(n)
 
    networks = []
    for _ in range(m):
        input_str = input()
        nums = list(map(int, input_str.split()))
        if nums[3] == 1:
            if uf.find(nums[0]) != uf.find(nums[1]):
                uf.union(nums[0], nums[1])
        else:
            networks.append(nums)
 
    networks.sort(key=lambda x: x[2])
 
    result = 0
    i = 0
    while True:
        if i >= len(networks):
            break
        else:
            if uf.find(networks[i][0]) != uf.find(networks[i][1]):
                uf.union(networks[i][0], networks[i][1])
                result += networks[i][2]
                if uf.get_count() == n - 1:
                    break
        i += 1
 
    if uf.get_count() != n - 1:
        result = -1
    print(result)

JAVA题解代码

import java.util.*;

class Main {
    static int[] fa = new int[200];
    static List<Integer[]> a = new ArrayList<>();
    
    // 合并两个集合，返回是否成功合并
    public static int merge(int x , int y){
        int fx = getfa(x);
        int fy = getfa(y);
        if (fx == fy) return 0;
        fa[fx] = fy;
        return 1;
    }
    
    // 使用路径压缩找到节点x的根节点
    public static int getfa(int x){
        if (fa[x] == x) return x;
        return fa[x] = getfa(fa[x]);
    }
    
    public static void init (){
        // 初始化并查集
        for (int i = 1 ; i < fa.length ; i++){
            fa[i] = i;
        }
    }
    public static void main (String [] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取节点数
        int m = sc.nextInt(); // 读取边数
        
        init();
        
        for (int i = 1 ; i <= m ; i++){
            int x = sc.nextInt(); // 边的起始节点
            int y = sc.nextInt(); // 边的结束节点
            int z = sc.nextInt(); // 边的权重
            int p = sc.nextInt(); // 是否预先连接的标志
            
            if (p == 1) merge(x , y); // 如果标志为1，直接合并两个节点
            else {
                a.add(new Integer[]{x , y , z}); // 否则将边加入到边列表中
            }
        }
        
        // 按照边的权重进行排序
        a.sort((a , b) -> {
            return a[2].compareTo(b[2]);
        });
        
        int ans = 0;
        for (Integer[] x : a){
            if (merge(x[0] , x[1]) == 1) ans += x[2]; // 如果成功合并两个节点，累加权重
        }
        
        // 判断所有节点是否联通
        boolean ok = true;
        for(int i = 1 ; i <= n ; i++) {
        	if(getfa(i) != getfa(1)) ok = false;
        }
        
        if (ok) {
        	System.out.println(ans); // 如果所有节点联通，输出最小花费
        }
        else {
        	System.out.println(-1); // 否则输出-1
        }
        
        return ;
    }
}

C/C++题解代码

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
class UF {
    vector<int> root;
    vector<int> rank;
    int count;
 
public:
    UF(int size) {
        root.resize(size + 1);
        rank.resize(size + 1);
        count = 0;
        for (int i = 0; i < size + 1; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }
 
    int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }
 
    void union(int x, int y) {
        root[find(x)] = find(y);
        count += 1;
    }
 
    int get_count() {
        return count;
    }
};
 
int main() {
    int n, m;
    cin >> n >> m;
    cin.ignore();
 
    UF uf(n);
 
    vector<vector<int>> networks;
    for (int i = 0; i < m; i++) {
        string input_str;
        getline(cin, input_str);
        stringstream ss(input_str);
        vector<int> nums;
        int num;
        while (ss >> num) {
            nums.push_back(num);
        }
        if (nums[3] == 1) {
            if (uf.find(nums[0]) != uf.find(nums[1])) {
                uf.union(nums[0], nums[1]);
            }
        } else {
            networks.push_back({nums[0], nums[1], nums[2]});
        }
    }
 
    sort(networks.begin(), networks.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
    });
 
    int result = 0;
    int i = 0;
    while (true) {
        if (i >= networks.size()) {
            break;
        } else {
            if (uf.find(networks[i][0]) != uf.find(networks[i][1])) {
                uf.union(networks[i][0], networks[i][1]);
                result += networks[i][2];
                if (uf.get_count() == n - 1) {
                    break;
                }
            }
        }
        i += 1;
    }
 
    if (uf.get_count() != n - 1) {
        result = -1;
    }
    cout << result << endl;
 
    return 0;
}

JS题解代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    // write your code here!

    const fa = Array.from({ length: 200 }, (_, i) => i);
    const a = [];
    function getfa(x) {
        if (fa[x] == x) {
            return x;
        }
        fa[x] = getfa(fa[x]);
        return fa[x];
    }
    // 合并两个集合，返回是否成功合并
    function merge(x, y) {

        const fx = getfa(x);
        const fy = getfa(y);
        if (fx == fy) {
            return 0;
        }
        fa[fx] = fy;
        return 1;
    }

    function init() {
        // 初始化并查集
        for (let i = 1; i < 200; i++) {
            fa[i] = i;
        }
    }

    const n = Number(lines[0]);
    const m = Number(lines[1]);

    init();

    for (let i = 1; i <= m; i++) {
        const [x, y, z, p] = lines[i + 1].trim().split(' ').map(Number); // 读取边的起始节点、结束节点、权重和标志

        if (p === 1) {
            merge(x, y); // 如果标志为1，直接合并两个节点
        } else {
            a.push([x, y, z]); // 否则将边加入边列表
        }
    }

    // 按边的权重排序
    a.sort((a, b) => a[2] - b[2]);

    let ans = 0;
    for (const x of a) {
        if (merge(x[0], x[1]) == 1) {
            ans += x[2]; // 如果成功合并两个节点，累加权重
        }
    }

    // 判断所有节点是否联通
    let ok = true;
    for (let i = 1; i <= n; i++) {
        if (getfa(i) !== getfa(1)) {
            ok = false;
            break;
        }
    }

    if (ok) {
        console.log(ans); // 如果所有节点联通，输出最小花费
    } else {
        console.log(-1); // 否则输出-1
    }
});

代码OJ评判结果
通过测试点

四.代码讲解(Java&Python&C++&JS分别讲解)

Python题解代码解析:

  1. UF类的定义： 定义了一个并查集（Union-Find）类，包括构造函数__init__用于初始化并查集，find用于查找节点所属的集合的根节点，union用于合并两个集合，get_count用于获取当前集合的数量。

  2. 主程序部分：

    • 通过输入读取基站的个数 n 和具备光纤直连条件的基站对的数目 m。
    • 创建并初始化并查集 uf，表示每个基站初始时独立成一个集合。
    • 通过循环读取基站对的信息，如果已存在光纤连接，则直接在并查集中进行合并操作；否则，将基站对的信息添加到 networks 列表中。
    • 对 networks 列表按照光纤成本进行升序排序。
    • 通过循环遍历排序后的基站对，如果两个基站不在同一集合中，则将它们连接，并累加连接的成本。直到所有基站都联通或者所有可能的连接都尝试完毕。
    • 如果最终连接的基站数量等于总基站数量减一，则说明成功建设互联互通的5G网络，输出累计的最小成本；否则，输出-1。

JAVA题解代码解析:

  1. 全局变量定义： 定义了一个静态数组 fa 用于存储每个节点的父节点，一个列表 a 用于存储未连接的边的信息。

  2. merge方法： 合并两个集合的方法，返回是否成功合并。

  3. getfa方法： 使用路径压缩找到节点 x 的根节点。

  4. init方法： 初始化并查集，将每个节点的父节点设为自己。

  5. 主程序部分：

    • 通过输入读取节点数 n 和边数 m。
    • 初始化并查集。
    • 循环读取边的信息，如果预先连接标志为1，则直接合并两个节点；否则，将边的信息加入列表 a。
    • 对列表 a 按照边的权重进行排序。
    • 遍历排序后的边，如果成功合并两个节点，则累加权重。
    • 判断所有节点是否联通，如果是则输出最小花费，否则输出-1。

C/C++题解代码解析:

  1. UF类的定义： 与Python中相同，定义了一个并查集（Union-Find）类。

  2. 主程序部分：

    • 通过输入读取基站的个数 n 和具备光纤直连条件的基站对的数目 m。
    • 创建并初始化并查集 uf。
    • 循环读取基站对的信息，如果已存在光纤连接，则直接在并查集中进行合并操作；否则，将基站对的信息添加到 networks 列表中。
    • 对 networks 列表按照光纤成本进行升序排序。
    • 通过循环遍历排序后的基站对，如果两个基站不在同一集合中，则将它们连接，并累加连接的成本。直到所有基站都联通或者所有可能的连接都尝试完毕。
    • 如果最终连接的基站数量等于总基站数量减一，则说明成功建设互联互通的5G网络，输出累计的最小成本；否则，输出-1。

JS题解代码解析:

  1. 全局变量定义： 定义了一个数组 fa 用于存储每个节点的父节点，一个列表 a 用于存储未连接的边的信息。

  2. merge方法： 合并两个集合的方法，返回是否成功合并。

  3. getfa方法： 使用路径压缩找到节点 x 的根节点。

  4. init方法： 初始化并查集，将每个节点的父节点设为自己。

  5. 主程序部分：

    • 通过输入读取节点数 n 和边数 m。
    • 初始化并查集。
    • 循环读取边的信息，如果预先连接标志为1，则直接合并两个节点；否则，将边的信息加入列表 a。
    • 对列表 a 按照边的权重进行排序。
    • 遍历排序后的边，如果成功合并两个节点，则累加权重。
    • 判断所有节点是否联通，如果是则输出最小花费，否则输出-1。

寄语

标签：JAVA,Python,题解,find,networks,int,基站,uf,节点
From： https://blog.csdn.net/shrgegrb/article/details/137459419

相关文章

  • 项目排期【华为OD机试】(JAVA&Python&C++&JS题解)
    一.题目项目组共有N个开发人员，项目经理接到了M个独立的需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。假定各个需求直接无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。输入描述：第一行输入为M个需......
  • 找城市【华为OD机试】(JAVA&Python&C++&JS题解)
    一.题目-找城市一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。当切断通往某个城市i的所有道路后，地图上将分为多个连通的城市群，设该城市i的聚集度为DPi（DegreeofP......
  • 电脑病毒感染【华为OD机试】(JAVA&Python&C++&JS题解)
    一.题目-电脑病毒感染一个局域网内有很多台电脑，分别标注为0-N-1的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用t表示。其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间。如果最后有电脑不会感染，则返回-1给定一个数组times表示......
  • 两个字符串间的最短路径问题【华为OD机试】(JAVA&Python&C++&JS题解)
    一.题目-两个字符串间的最短路径问题给定两个字符串，分别为字符串A与字符串B。例如A字符串为ABCABBA，B字符串为CBABAC可以得到下图m*n的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1，映射成坐标系如下图。从原点(0,0)到(0,A)为水平边，距离为1，从(0,A)......
  • Python学习（八）：python面向对象编程
    文章目录python面向对象编程类的定义类的实例化类的静态变量与静态方法类的静态变量类的静态方法@staticmethod类的类方法@classmethod类的继承单继承多继承多层继承类方法的重写类方法的重载调用父类的方法super函数python面向对象编程面向对象(ObjectOriented)......
  • Python学习（七）：基础运算符与表达式【详解】
    文章目录python基础运算符与表达式运算符与表达式的优先级算术运算符（四则运算）算术运算符（取余/模、乘方）关系比较运算符位运算符逻辑运算符赋值运算符、复合赋值运算符条件表达式await序列切片表达式星号表达式yield表达式lambda表达式python基础运算符与表达式运算符......
  • Python量化交易系统实战--量化交易入门
    作者：麦克煎蛋  出处：https://www.cnblogs.com/mazhiyong/转载请保留这段声明，谢谢！ 这个系列的文章主要是基于慕课网的量化交易学习的笔记，顺便也加了自己的一些理解和优化。一边学一边写，回头再梳理。  量化交易是指以先进的数学模型替代人为的主观判断，利用计算机技术从庞......
  • 10 Python进阶：MongoDB
    MongoDb介绍MongoDB是一个基于分布式架构的文档数据库，它使用JSON样式的数据存储，支持动态查询，完全索引。MongoDB是NoSQL数据库的一种，主要用于处理大型、半结构化或无结构化的数据。以下是MongoDB数据库的一些关键特点和优势：分布式架构:MongoDB可以运行在多个服务器上，以......
  • 基于R、Python的Copula变量相关性分析及AI大模型应用
    在工程、水文和金融等各学科的研究中，总是会遇到很多变量，研究这些相互纠缠的变量间的相关关系是各学科的研究的重点。虽然皮尔逊相关、秩相关等相关系数提供了变量间相关关系的粗略结果，但这些系数都存在着无法克服的困难。例如，皮尔逊相关系数只能反映变量间的线性相关，而秩相关则......
  • java中大型医院HIS系统源码 Angular+Nginx+SpringBoot云HIS运维平台源码
    java中大型医院HIS系统源码Angular+Nginx+SpringBoot云HIS运维平台源码云HIS系统是一款满足基层医院各类业务需要的健康云产品。该产品能帮助基层医院完成日常各类业务，提供病患预约挂号支持、病患问诊、电子病历、开药发药、会员管理、统计查询、医生工作站和护士工作站等一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99