5G网络建设 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

现需要在某城市进行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站点2向铺设,其成本为1

题解

最小生成树的问题，可以使用 Kruskal 算法进行求解。

初始化并查集，每个基站初始时属于一个独立的集合。
将已经存在光纤连接的基站合并到同一个集合中。
将未连接的光纤按照成本从小到大排序。
遍历排序后的光纤，将两个基站连接，如果两个基站已经属于同一个集合，则不连接。
判断所有基站是否属于同一个集合，如果是，则输出总成本，否则输出-1。

Kruskal 算法的步骤：

初始化： 将每个顶点视为一个独立的集合，每个集合中只包含一个顶点。将图中的所有边按照权值从小到大排序。
遍历边： 从权值最小的边开始遍历，如果该边连接的两个顶点不在同一个集合中，则选择这条边，并将这两个顶点所在的集合合并为一个集合。重复此步骤直到所有顶点都在同一个集合中。
输出结果： 最终得到的就是最小生成树。

Java

import java.util.Comparator;
import java.util.Scanner;
import java.util.Vector;
/**
 * @author code5bug
 */
class Main {

    static int[] fa;

    static int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    static void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        fa[fx] = fy;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 基站个数, 具备光纤直连条件的基站对的数目
        int N = scanner.nextInt(), M = scanner.nextInt();
        
        fa = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            fa[i] = i;
        }

        Vector<Plan> plans = new Vector<>();
        for (int i = 0; i < M; i++) {
            Plan p = new Plan();
            p.x = scanner.nextInt();  p.y = scanner.nextInt();
            p.z = scanner.nextInt();  p.p = scanner.nextInt();

            // 已经存在光纤
            if (p.p == 1) {
                merge(p.x, p.y);
            } else {
                plans.add(p);
            }
        }

        plans.sort(Comparator.comparingInt(a -> a.z));

        int cost = 0;
        for (Plan p : plans) {
            // 没有连接则连接上
            if (find(p.x) != find(p.y)) {
                cost += p.z;
                merge(p.x, p.y);
            }
        }

        // 所有基站是否连接
        boolean allConnected = true;
        for (int i = 1; i <= N; i++) {
            if (find(i) != find(1)) {
                allConnected = false;
                break;
            }
        }

        System.out.println(allConnected ? cost : -1);
    }
}

class Plan {
    int x, y; // 基站的编号
    int z, p; // 架设光纤的成本, 是否已存在光纤连接，0表示未连接1表示已连接
}

Python

class Plan:
    def __init__(self, x, y, z, p):
        self.x = x  # 基站的编号
        self.y = y  # 基站的编号
        self.z = z  # 架设光纤的成本
        self.p = p  # 是否已存在光纤连接，0表示未连接，1表示已连接


def find(x, fa):
    if fa[x] == x:
        return x
    fa[x] = find(fa[x], fa)
    return fa[x]


def merge(x, y, fa):
    fx, fy = find(x, fa), find(y, fa)
    fa[fx] = fy


def main():
    N, M = int(input()), int(input())

    fa = [i for i in range(N+1)]

    plans = []
    for _ in range(M):
        x, y, z, p = map(int, input().split())
        if p == 1:
            merge(x, y, fa)
        else:
            plans.append(Plan(x, y, z, p))

    plans.sort(key=lambda p: p.z)

    cost = 0
    for p in plans:
        if find(p.x, fa) != find(p.y, fa):
            cost += p.z
            merge(p.x, p.y, fa)

    all_connected = all(find(i, fa) == find(1, fa) for i in range(1, N+1))

    print(cost if all_connected else -1)


if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

struct plan{
    int x, y; // 基能的编号
    int z, p; // 架设光纤的成本, 是否已存在光纤连接，0表示未连接1表示已连接
};

int fa[30];

int find(int x){
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y){
    int fx = find(x), fy = find(y);
    fa[fx] = fy;
}

int main(){
    int N, M;

    // 基站个数, 具备光纤直连条件的基站对的数目
    cin >> N >> M;

    for(int i=1;i<=N;i++) fa[i] = i;

    vector<plan> plans;
    for(int i=0;i<M;i++){
        plan p;
        cin >> p.x >> p.y >> p.z >> p.p;

        // 已经存在光纤
        if(p.p == 1) merge(p.x, p.y);
        else plans.push_back(p);
    }

    sort(plans.begin(), plans.end(), [](plan a, plan b){
        return a.z < b.z;
    });


    int cost = 0;
    for(auto& p : plans){
        // 没有连接则连接上
        if(find(p.x) != find(p.y)){
            cost += p.z;
            merge(p.x, p.y);
        }
    }

    // 所有基站是否连接
    bool all_connected = true;
    for(int i=1;i<=N;i++){
        if(find(i) != find(1)){
            all_connected = false;
            break;
        }
    }

    cout << (all_connected ? cost : -1) << endl;

    return 0;
}