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)