华为OD统一考试- 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
用例
输入 | 3 3 1 2 3 0 1 3 1 0 2 3 5 0 |
输出 | 4 |
说明 | 只需要在1,2以及1,3基站之间铺设光纤,其成本为3+1=4 |
输入 | 3 1 1 2 5 0 |
输出 | -1 |
说明 | 3基站无法与其他基站连接,输出-1 |
输入 | 3 3 1 2 3 0 1 3 1 0 2 3 5 1 |
输出 | 1 |
说明 | 2,3基站已有光纤相连,只要在1,3基站之间铺设光纤,其成本为1 |
题目解析
(下图中,虚线代表节点之间可以铺设光纤,但是还没有铺设,实线表示已经铺好了)
用例1图示
用例2图示
用例3图示
本题是经典的最小生成树问题
生成树概念
而在了解最小生成树概念前,我们需要先了解生成树的概念:
在无向连通图中,生成树是指包含了全部顶点的极小连通子图。
生成树包含原图全部的n个顶点和n-1条边。(注意,边的数量一定是n-1)
比如下面无向连通图例子:
根据生成树概念,我们可以基于上面无向连通图,产生多个生成树,下面举几个生成树例子:
如上图我们用n-1条橙色边连接了n个顶点。这样就从无向连通图中产生了生成树。
为什么生成树只能由n-1条边呢?
因为少一条边,则生成树就无法包含所有顶点。多一条边,则生成树就会形成环。
而生成树最重要的两个特性就是:
1、包含所有顶点
2、无环
最小生成树概念
了解了生成树概念后,我们就可以进一步学习最小生成树了。
我们回头看看无向连通图,可以发现每条边都有权重值,比如v1-v2权重值是6,v3-v6权重值是4。
最小生成树指的是,生成树中n-1条边的权重值之和最小。
那么如何才能准确的找出一个无向连通图的最小生成树呢?
有两种算法:Prim算法和Kruskal算法。
Prim算法是基于顶点找最小生成树。Kruskal是基于边找最小生成树。
Prim算法
首先,我们介绍Prim算法:
我们可以选择无向连通图中的任意一个顶点作为起始点,比如我们选v1顶点为起始点
从v1顶点出发,有三条边,我们选择权重最小的1,即将v1-v3相连
此时我们需要将v1-v3看成一个整体,然后继续找这个整体出发的所有边里面的最小的,
可以发现为最小权重为4,因此,将v3-v6相连
接着将v1-v3-v6看出一个整体,找这个整体出发的所有边里面的最小的,可以找到最小权重2,因此将v6-v4相连
但是接下来,我们会发现,从v1-v3-v6-v4整体出发的所有边里面同时有三个最小权重5,那么该如何选择呢?
其实不难看出,如果选择v4-v3,或者v4-v1相连,则对应的生成树就形成了环结构,因此就不符合生成树特性了,因此我们只能选择v3-v2。
(注意:如果有多个相同的最小权重边可选,并且都不会产生环结构,则可以选择其中任意一条边,最终得到结果都是最小生成树)
其实,不仅仅在上面遇到相同权重边时,需要判断是否形成环,在前选择每一条边时都需要判断是否形成环,一旦选择的边能够形成环,那么我们就应该舍弃它,选择第二小的权重边,并继续判断。
按照上面逻辑,我们可以继续找到v1-v2-v3-v4-v6整体出发所有边中的最小权重边3,即将v2-v5相连,并且连接后不会形成环
此时选择的边数已经达到了n-1条,因此可以结束逻辑,而现在得到的就是最小生成树。我们可以将这个最小生成数的所有边的权重值之和计算出来为15。
上面这种基于顶点的找最小生成树的方式就是Prim算法。
关于Prim算法具体实现细节请看代码实现,已添加详细注释。
Kruskal算法
接下来介绍Kruskal算法:
Kruskal算法要求我们将所有的边按照权重值升序排序,因此可得:
首先,我们将权重最小的边v1-v3加入,得到下图
接着将下个最小权重2的边v4-v6加入
接着继续加最小权重边
此时边数已经达到n-1,而刚好这个过程中也没有环的形成,因此得到的就是最小生成树。
但是这里有巧合因素在里面,因为最后一步中,最小权重5的边有多条,如果并不是v2-v3排在前面呢,比如是v1-v4呢?
可以发现,形成了环,因此我们应该舍弃这条边,继续找剩下的最小权重边。最后总能找到v2-v3。
那么判断环的存在就是实现上面Prim算法和Kruskal算法的关键点!
其实,生成树就是一个连通分量,初始时,生成树这个连通分量只有一个顶点(Prim),或者两个顶点(Kruskal),后面会不断合入新的顶点进来,来扩大连通分量范围。
而连通分量可以使用并查集表示,
并查集本质就是一个长度为n的数组(n为无向图的顶点数),数组索引值代表图中某个顶点child,数组索引指向的元素值,代表child顶点的祖先顶点father。
初始时,每个child的father都是自己。即初始时,默认有n个连通分量。
比如 arr = [1,1,1,5,5,5] 数组就可以模拟出一个无向图
- 0顶点(索引值)的祖先是1顶点(元素值)
- 1顶点(索引值)的祖先是1顶点(元素值)
- 2顶点(索引值)的祖先是1顶点(元素值)
我们可以用father指代一个连通分量。比如上面arr = [1,1,1,5,5,5]就有两个连通分量,分别是father为1的连通分量和father为5的连通分量。
最小生成树中的顶点必然都处于同一个连通分量中,因此每加入一个新的顶点child_new,我们我们就可以看它的father是否已经是连通分量对应的father,如果是,则说明顶点child_new其实已经存在于最小生成树中了,因此就产生了环,比如下面例子:
上面右图绿色部分(对应连通图中橙色实线),则arr变为
上面右图黄色部分(对应连通图中黑色实线),即v4顶点的father改成v1,但是实际上v4的father已经是v1,那么此时如果再强行加入的话,那么就形成了环。
Prim算法和Kruskal算法的适用场景
Prim算法是基于节点操作的,因此Prim算法适用于节点少,边多的情况
Kruskal算法是基于边操作的,因此Kruskal算法适用于节点多,边少的情况。
本题解析
本题属于最小生成树的变种题,区别于板子题,本题中主要是存在一些已经关联好的节点。
比如下面连通图中,2-3是已经连通好的。
其实处理起来也很简单,对于已经关联了的节点,我们可以认为他们之间的边权为0。
即上图中,2-3虽然边权为5,但是由于已经关联好了,因此可以认为实际边权为0。
这样的话,本题就变成最小生成树的板子题了。
import Foundation func ODTest_2_14() { print("输入描述") print("第一行输入表示基站的个数N,其中:") print("0 < N ≤ 20") let N = Int(readLine() ?? "") ?? 0 print("第二行输入表示具备光纤直连条件的基站对的数目M,其中:") print("0 < M < N * (N - 1) / 2") let M = Int(readLine() ?? "") ?? 0 print("从第三行开始连续输入M行数据,格式为") print("X Y Z P") print("其中:") print("X,Y 表示基站的编号") print("0 < X ≤ N0 < Y ≤ NX ≠ Y") print("Z 表示在 X、Y之间架设光纤的成本") print("P 表示是否已存在光纤连接,0 表示未连接,1表示已连接") var XYZP: [[Int]] = [] for _ in 0 ..< M { var data = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 } XYZP.append(data) } print("X,Y 表示基站的编号") var graph: [[Int]] = Array(repeating: Array(repeating: Int.max, count: N + 1), count: N + 1) for i in 0 ..< M { let x = XYZP[i][0] let y = XYZP[i][1] let z = XYZP[i][2] let p = XYZP[i][3] if p == 0 { // x-y边权为z graph[x][y] = z graph[y][x] = z } else { // 对应已经联通的两点,可以理解为边权为0 graph[x][y] = 0 graph[y][x] = 0 } } print("如果给定条件,可以建设成功互联互通的5G网络,则输出最小的建设成本") print("\(prim(graph, N))") } func prim(_ graph: [[Int]], _ n: Int) -> Int { // 记录最小生成树的边权和 var minWeight = 0 // inTree[i] 表示 节点i 是否在最小生成树中 var inTree: [Bool] = Array(repeating: false, count: n + 1) // 初始时任选一个节点作为最小生成树的初始节点,这里选择节点1 inTree[1] = true // 记录最小生成树中点数量 var inTree_count = 1 // dis[i]表示 节点i 到最小生成树集合 的最短距离 var dis: [Int] = Array(repeating: 0, count: n + 1) for i in 1 ... n { // 初始时,最小生成树集合中只有节点1,因此其他节点到最小生成树的距离,其实就是到节点1的距离 dis[i] = graph[1][i] } // 如果最小生成树中点数量达到n个,则结束循环 while inTree_count < n { // 现在我们需要从未纳入最小生成树的点中,找到一个距离最小生成树最近的 // minDis 记录这个最近距离 var minDis = Int.max // idx 记录距离最小生成树minDis个距离的节点 var nodeIdx = 0 for i in 1 ... n { // 从未纳入最小生成树的点中,找到一个距离最小生成树最近的 if !inTree[i] && dis[i] < minDis { minDis = dis[i] nodeIdx = i } } // 如果nodeIdx == 0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Int.max,即不与最小生成树存在关联 if nodeIdx == 0 { // 则说明,当前所有点无法形成最小生成树 return -1 } inTree[nodeIdx] = true // 最小生成树需要纳入最短距离点nodeIdx inTree_count += 1 // 最小生成树中点数量+1 minWeight += dis[nodeIdx] // 更新最小生成树的权重和 // dis[i] 初始时记录的是节点i 到 节点1 的距离(初始的生成树中只有节点1) // 现在生成树纳入了新节点nodeIdx,则我们需要更新一下dis[i],即有可能某些点到最小生成树中的nodeIdx点距离更近 for i in 1 ... n { if !inTree[i] && graph[nodeIdx][i] < dis[i] { // 注意,这是一个累进过程,初始时dis[i]记录的是节点i到节点1的距离, // 之后,最小生成树纳入新点后,如果节点i到新点的距离更近,则dis[i]就更新为这个更短距离 // 总之,dis[i] 记录的是 节点 i 到最小生成树的最短距离 dis[i] = graph[nodeIdx][i] } } } return minWeight }