本文主要是介绍OD C卷 - 5G网络建设,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
5G网络建设 (200)
- 选取n个地点建设5G基站,地点编号1 -> n;
- 各个基站之间使用光纤连接,设计算法计算连通所有基站的最小成本;
- 基站的连通具有传递性,A->B连通,B->C连通,则A->C连通;
输入描述:
第一行输入基站个数n, 0< n <=20;
第二行输入已具备光纤连接的基站对数m;
第三行开始的m行,格式为 X Y Z P,X Y表示基站编号 1-n且不相等,Z表示XY之间的光纤成本(0, 100),P表示是否已存在光纤连接,0未连接,1已连接;
输出描述:
输出最小的建设成本(所有基站连通),无法建设完成输出-1;
示例1
输入:
3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出:
4
说明:只需在1、2及2、3之间建设光纤
示例2
输入:
3
1
1 2 5 0
输出:
-1
示例3
输入:
3
3
1 2 3 0
1 3 1 0
2 3 5 1
输出:
1
思路:
- 并查集,实现图连通;
- 并查集是一种高级数据结构,实现不相交集合的合并问题;
- 步骤:
- 初始化,每个节点的父(根)节点是自己;
- find查找,查找每个节点的父节点,如果父节点是自己则返回自己,否则递归查找其父节点的父节点,将最终的父节点(即父为自己的节点)赋值作为前一个节点的父节点,并返回;
- 合并,两个节点的父节点不一样,则合并,即其中一个节点所在集合的父节点->的父节点设置为另一个节点所在集合的父节点;
- 本题思路:
- 已连接的,只需合并,edges_num += 1;
- 未连接的需要按照成本升序排序,然后依次建立连接,同时edges_num += 1 and total_cost += cur_cost;
- edges_num == n - 1 则连通,否则无法连通;
class UF: # 并查集def __init__(self, n): # 1 初始化# 每个节点的父节点是自己self.fa = [i for i in range(n + 1)]self.edges = 0 # n个节点 n-1条边可以连通def find(self, x): # 2 查询节点的根# 当前节点的根,根为自己则returnif x == self.fa[x]:return x# 否则 递归查询根 (路径压缩)self.fa[x] = self.find(self.fa[x])return self.fa[x]def union(self, x, y): # 3 合并,两个集合的根不同,则合并self.fa[self.find(x)] = self.find(y)self.edges += 1 # 边数+1def get_edges(self):return self.edgesn = int(input()) # 总节点数
m = int(input()) # 连接数对
uf = UF(n)
networks = []for i in range(m): # m行data = [int(x) for x in input().strip().split()]if data[-1] == 1:# 已建立连接,使用并查集 进行合并(边+1 不计成本)if uf.find(data[0]) != uf.find(data[1]): # 根节点不同 则合并uf.union(data[0], data[1])else:# 尚未建立连接networks.append([data[0], data[1], data[2]]) # 成本即权重# 按照成本 升序排序
networks = sorted(networks, key=lambda x: x[2])total_cost = 0 # 成本
i = 0 # networks 列表索引
while True:if i >= len(networks):breakelse:# 对于尚未连接的基站,进行并查集 合并, 成本累加起来if uf.find(networks[i][0]) != uf.find(networks[i][1]): # 根节点不同,则合并# 不相交集合 的合并uf.union(networks[i][0], networks[i][1])# 成本累加total_cost += networks[i][2]# 连接的边数if uf.get_edges() == n - 1: # n个节点 只需n-1条边 连通break# 继续合并第二组i += 1if uf.get_edges() != n - 1:total_cost = -1print(total_cost)
这篇关于OD C卷 - 5G网络建设的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!