题解 | #Freckles#
Freckles
https://www.nowcoder.com/practice/41b14b4cd0e5448fb071743e504063cf
import math # 最小生成树 prim # 边选择方式:普里姆算法也是一种贪心算法,但是它是基于 节点 的,每次选择与当前已选节点集合相连的且权重最小的边,确保连通性。 # 实现细节:普里姆算法通常使用 优先队列(Priority Queue)来管理节点之间的边,以快速找到下一条最小权重的边。 def distance(point1, point2): """计算两点之间的距离""" return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2) def prim(points): # 点的数量 n = len(points) # 邻接矩阵:(i,j)表示 点i到点j的距离 adj_matrix = [[0] * n for _ in range(n)] for i in range(n): for j in range(i + 1, n): dist = distance(points[i], points[j]) adj_matrix[i][j] = adj_matrix[j][i] = dist # 到当前最小生成树的最小距离:默认+∞ min_weight = [math.inf] * n # 标记是否已经加入到最小生成树中 visited = [False] * n # 选择第一个点作为起点 min_weight[0] = 0 # 总长度 total_length = 0 for _ in range(n): u = -1 # 选择一个未访问的点使得距离最小 for i in range(n): # 如果 该点未被访问 且(访问的是第一个点 或 当前存在更短路径) if not visited[i] and (u == -1 or min_weight[i] < min_weight[u]): u = i visited[u] = True # 标记为已访问 total_length += min_weight[u] # 累加总长度 # 更新未访问的点到当前最小生成树的距离 for v in range(n): if not visited[v] and adj_matrix[u][v] < min_weight[v]: min_weight[v] = adj_matrix[u][v] # print(sum(min_weight)) return total_length # 输入处理 n = int(input()) points = [tuple(map(float, input().split())) for _ in range(n)] # 计算最小生成树的总长度并输出 print(f"{prim(points):.2f}")
最小生成树