题解 | #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}")

最小生成树

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
点赞 评论 收藏
分享
点赞 评论 收藏
分享
白火同学:大二有这水平很牛了,可以适当对关键信息加粗一点,比如关键技术、性能指标之类的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务