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

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

现需要在某城市进行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. 初始化并查集，每个基站初始时属于一个独立的集合。

2. 将已经存在光纤连接的基站合并到同一个集合中。

3. 将未连接的光纤按照成本从小到大排序。

4. 遍历排序后的光纤，将两个基站连接，如果两个基站已经属于同一个集合，则不连接。

5. 判断所有基站是否属于同一个集合，如果是，则输出总成本，否则输出-1。

Kruskal 算法的步骤：

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

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)