day62 53.寻宝

53. 寻宝（第七期模拟笔试） 

题目描述

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。 

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

输入描述

第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。

接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。

输出描述

输出联通所有岛屿的最小路径总距离 

输入示例

7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1

输出示例

6

提示信息

数据范围：
2 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;

如下图，可见将所有的顶点都访问一遍，总距离最低是6.

  

第一种方法（prim算法）：

v, e = map(int, input().split())grid = [[10001] * (v + 1) for _ in range(v + 1)]for i in range(e):x, y, k = map(int, input().split())grid[x][y] = kgrid[y][x] = kmin_dist = [10001] * (v + 1) # 所有非生成树节点到生成树的距离is_tree = [False] * (v + 1) # 这个节点是否在树里# 有v个节点，最少的边树是v-1, 所以循环v - 1次就可以建立起一个v个节点的图
for _ in range(v - 1):# prim三部曲，第一步：选距离生成树最近节点cur = -1min_val = float('inf')for i in range(1, v + 1): # 从1-v，从1开始到第v个节点# 选取条件：# 1.不在树里# 2.距离最小生成树最近的节点if not is_tree[i] and min_dist[i] < min_val:min_val = min_dist[i]cur = i# prim三部曲，第二部：将选择的节点加入到树中is_tree[cur] = True# prim三部曲，第三部：更新非生成树节点到生成树的距离（即min_dist数组）# cur节点加入之后，最小生成树加入了新节点，那么所有节点到最小生成树的距离（即min_dist数组）更新一下# 由于cur节点是新加入的，所以只需要关心与cur节点相连的 非生成树节点是否比 原来非生成树节点到最小生成树的距离小for i in range(1, v + 1):# 更新条件：# 1.节点是非生成树的节点# 2.与cur相连的某节点的权值 比 某节点到最小生成树的距离 小if not is_tree[i] and grid[cur][i] < min_dist[i]:min_dist[i] = grid[cur][i]result = 0   
for i in range(2, v + 1): # 不计第一个节点，因为统计的是边的权值，n个节点，有n - 1条边result += min_dist[i]print(result)    

第二种方法（kruskal算法）：

class Edge:# l,r为 边两边的节点，val为边的数值def __init__(self, l, r, val):self.l = lself.r = rself.val = valn = 10001
father = list(range(n))# 并查集初始化
def init():global fatherfather = list(range(n))# 并查集的寻根操作
def find(u):if u == father[u]:return uelse:father[u] = find(father[u]) # 路径压缩return father[u]# 并查集加入集合
def join(u, v):u = find(u)v = find(v)if u == v:returnfather[v] = udef main():v, e = map(int, input().split())edges = []for _ in range(e):v1, v2, val = map(int, input().split())edges.append(Edge(v1, v2, val))# 执行kruscal算法# 按边的权值对边进行从小到大的排序edges.sort(key = lambda edge: edge.val)# 并查集初始化init()result_val = 0for edge in edges:x = find(edge.l)y = find(edge.r)if x != y:result_val += edge.valjoin(x, y)print(result_val)if __name__ == '__main__':main()