5G网络建设

题目描述

现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N，接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间架设光纤的成本各不相同，且有些节点之间已经存在光纤相连，请你设计算法，计算出能联通这些基站的最小成本是多少。
注意:基站的联通具有传递性，入基站A与基站B架设了光纤，基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通

输入描述:

第一行输入表示基站的个数N，其中0<N<=20
第二行输入表示具备光纤直连条件的基站对的数目M，其中0<M<N*(N-1)/2
从第三行开始连续输入M行数据，格式为XYZP，其中XY表示基站的编号，0<X<=N，0<Y<=N且x不等于y，Z表示在XY之间架设光纤的成本，其中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

 解题思路：

这个问题可以使用最小生成树算法来解决，其中最常用的算法是Kruskal算法。

1. 首先，我们将所有基站之间的连接按照成本进行排序。
2. 创建一个并查集数据结构，用于判断基站之间的连通性。
3. 从连接成本最低的边开始遍历，依次判断两个基站是否已经连通，如果未连通则合并它们，并累加连接成本。
4. 一直进行上述步骤，直到所有的基站都连通或者遍历完所有的边。
5. 如果最终连通的基站数量等于总的基站数量减1（即生成了一棵包含所有基站的树），则结果为累积的连接成本；否则，说明无法建设一个互联互通的网络，结果为-1。

通过排序边、使用并查集判断连通性，可以找到能够联通这些基站的最小成本。

Java实现 

package org.example.od.two;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class T1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 基站个数
        int M = scanner.nextInt(); // 光纤直连条件的基站对数
        int[][] connections = new int[M][4]; // 存储基站连接信息，每行格式为XYZP，表示基站X与基站Y之间架设光纤的成本为Z，是否已存在光纤连接为P

        for (int i = 0; i < M; i++) {
            connections[i][0] = scanner.nextInt();
            connections[i][1] = scanner.nextInt();
            connections[i][2] = scanner.nextInt();
            connections[i][3] = scanner.nextInt();
        }

        int result = minimumCostToBuildNetwork(N, M, connections);
        System.out.println(result);
    }

    public static int minimumCostToBuildNetwork(int N, int M, int[][] connections) {
        Arrays.sort(connections, Comparator.comparingInt(a -> a[2])); // 按照连接成本对边进行排序

        UnionFind uf = new UnionFind(N); // 创建并查集实例
        int totalCost = 0; // 记录总的连接成本
        int count = 0; // 记录已经连通的基站对数

        for (int[] connection : connections) {
            int a = connection[0] - 1; // 基站编号从1开始，转换为数组索引需要减1
            int b = connection[1] - 1;
            int cost = connection[2]; // 连接成本
            int connected = connection[3]; // 是否已存在光纤连接

            if (connected == 1 || uf.union(a, b)) { // 如果已存在连接或者成功合并两个基站
                totalCost += cost; // 累加连接成本
                count++; // 基站对数加1
            }

            if (count == N - 1) { // 如果已连通的基站对数等于总的基站数减1，则说明已经构建了一棵包含所有基站的树，不需要继续遍历边
                break;
            }
        }

        if (count == N - 1) {
            return totalCost; // 返回累计的连接成本
        } else {
            return -1; // 返回-1表示无法建设互联互通的网络
        }
    }

    // 并查集数据结构
    static class UnionFind {
        private int[] parent; // 记录父节点
        private int[] rank; // 记录树的深度

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i; // 初始化每个节点的父节点为自身
                rank[i] = 0; // 初始化每个节点的深度为0
            }
        }

        // 查找节点的根节点（代表元素）
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 使用路径压缩优化，将节点直接连接到根节点，减小树的高度
            }
            return parent[x];
        }

        // 合并两个节点所在的树
        public boolean union(int x, int y) {
            int rootX = find(x); // 找到x的根节点
            int rootY = find(y); // 找到y的根节点

            if (rootX == rootY) {
                return false; // 如果根节点相同，说明两个节点已经连通，无需再合并
            }

            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY; // 将深度较小的树连接到深度较大的树上
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX; // 如果深度相同，则将y所在的树连接到x所在的树上，并将x所在的树的深度加1
                rank[rootX]++;
            }

            return true; // 返回true表示成功合并两个节点
        }
    }
}

最小生成树算法

最小生成树算法是一种用于在给定的图中找到一棵包含所有顶点的树，并且树的边的权重之和最小的算法。

常见的最小生成树算法有Prim算法和Kruskal算法，下面我会简要解释这两种算法的原理和步骤。

1. Prim算法：

   • 首先选择一个起始顶点，将其标记为已访问。
   • 从已访问的顶点集合中选择一条边，该边连接的顶点一个属于已访问的顶点集合，另一个不属于。选择的边的权重应该是连接这两个顶点的边中最小的。
   • 将选择的边加入到最小生成树中，并将连接的顶点标记为已访问。
   • 重复上述步骤，直到最小生成树包含了所有顶点。

2. Kruskal算法：

   • 将图中的所有边按照权重进行排序。
   • 从权重最小的边开始遍历，如果这条边连接的两个顶点不在同一个连通分量中（即不会形成环），则将这条边加入到最小生成树中，并将这两个顶点合并到同一个连通分量中。
   • 重复上述步骤，直到最小生成树包含了所有顶点。

这两种算法都能找到一棵最小生成树，但是它们的实现思路略有不同。Prim算法以顶点为中心，从已访问的顶点集合中选择边；而Kruskal算法以边为中心，按照权重逐步选择边。

 Prim算法：

当使用Prim算法时，我们会从一个起始顶点开始，然后逐步扩展树以包含更多的顶点，直到所有顶点都被连接到这棵树中。以下是Prim算法的通俗易懂解释和演示：

1. 选择起始顶点：随机选择一个顶点作为起始顶点，并将其标记为已访问。

2. 找到最短边：从已访问的顶点集合中找到一条连接到未访问顶点的最短边，即权重最小的边。

3. 将新顶点加入树：将这条最短边连接的未访问顶点加入树中，并将其标记为已访问。

4. 重复步骤：重复步骤2和步骤3，直到所有顶点都被连接到树中为止。

下面通过一个简单的示例来演示Prim算法的执行过程：

假设有一个图，其中包含了5个顶点：A、B、C、D、E，以及它们之间的边和对应的权重。我们可以将这个图描述如下：

• 顶点A与顶点B之间有一条权重为3的边。
• 顶点A与顶点C之间有一条权重为5的边。
• 顶点A与顶点E之间有一条权重为6的边。
• 顶点B与顶点D之间有一条权重为4的边。
• 顶点C与顶点E之间有一条权重为8的边。
• 顶点D与顶点E之间有一条权重为7的边。

1. 选择起始顶点A，并将其标记为已访问。
2. 找到A连接到B的边权重最小，为2，因此将B加入树中。
3. 现在考虑连接到A或B的边，C和E都与A相连，但选择AC权重最小为5，将C加入树中。
4. 接着找到连接到A、B或C的最短边，选择AD或DE其中之一，假设选取AD权重为1，将D加入树中。
5. 继续这个过程，直到所有顶点都被连接到树中。

通过以上步骤，Prim算法会构建出一棵最小生成树，该树包含了所有的顶点，并且总权重最小。

 Kruskal算法

Kruskal算法是一种常用于求解最小生成树的算法，它的思路比较简单易懂。下面我将用通俗易懂的方式解释并演示Kruskal算法的执行步骤：

1. 初始化：将图中的所有边按照权重从小到大进行排序。

2. 选择边：按照排好序的顺序，依次选择权重最小的边，如果这条边连接的两个顶点不在同一个连通分量中（即不会形成环），则将这条边加入最小生成树中。

3. 更新连通分量：将连接的两个顶点合并到同一个连通分量中，表示它们已经连接在一起。

4. 重复步骤：重复步骤2和步骤3，直到最小生成树中包含了所有顶点。

下面通过一个简单的示例来演示Kruskal算法的执行过程：

假设我们有一个图，顶点分别是A、B、C、D、E，边的权重如下图所示：

• A-B: 2
• A-C: 5
• A-E: 6
• B-D: 4
• C-E: 8
• D-E: 7

1. 按照边权重从小到大的顺序排序，得到以下顺序：AB, BD, AE, DE, CE。
2. 选择权重为2的边AB，将顶点A和B加入最小生成树，同时它们被标记为同一个连通分量。
3. 选择下一条权重为4的边BD，将顶点D加入最小生成树，此时D与A、B在同一个连通分量中。
4. 选择权重为5的边AC，将顶点C加入最小生成树，同时与前面的顶点在同一个连通分量。
5. 选择权重为6的边AE，将顶点E加入最小生成树，此时所有顶点均在同一个连通分量中。
6. 最后选择权重为7的边DE或者权重为8的边CE，但由于会形成环，忽略这条边。

通过以上步骤，Kruskal算法会构建出一棵最小生成树，该树包含了所有的顶点，并且总权重最小。