当前位置: 首页 > article >正文

【蓝桥杯】1124修建公路1(Kruskal算法)

在这里插入图片描述

思路

找到能够连通所有城市的最小树即可,可用PrimKruscal
!!注意,m的范围是包括0的,可就是包含没有道路的情况,要单独输出0

code

import os
import sys

# 输入
n,m = map(int,input().split())
road = []
for i in range(m):
  u,v,w = list(map(int,input().split()))
  road.append([w,u,v]) # 存储道路信息

road.sort() # 按照道路长度(价格) 从小到大排序,优先选价格低的路
# 写一个并查集,用于查看两个城市是否已经相连
def find(x):
  if father[x] == x:
    return x
  father[x] = find(father[x])
  return father[x]  

father = list(range(n+1)) # 并查集父节点列表
min_ = 0 # 累积价格
flag = 0 # 用于判断是否全连接
cnt = 0 # 已连接的城市数
for ls in road:
  w,u,v = ls[0],ls[1],ls[2]
  fu = find(u)
  fv = find(v)
  if fu != fv:
    cnt+=1
    father[fv] = fu # 并查集合并
    min_ += w
  if cnt == n-1: # n个城市,最大n-1次连接即可全连接
    flag = 1 # 已全连接
    break # 跳出

if m==0:print(0)
elif flag:print(min_)
else:print(-1)

http://www.kler.cn/a/590000.html

相关文章:

  • 机器学习之激活函数
  • 文件解析漏洞靶场---解析详解
  • 利用hexo+github部署属于自己的个人博客网站(2025年3月所写)
  • 实现电商网站商品检索
  • UBuntu虚拟机上的redis服务突然消失了
  • 图形编辑器基于Paper.js教程25:材料测试矩阵功能的实现
  • [算法] 贪心--矩阵消除游戏
  • MyBatis SqlSession 是如何创建的? 它与 SqlSessionFactory 有什么关系?
  • 【Android】ListView控件在进入|退出小窗下的异常
  • 【xv6操作系统】页表与写时拷贝解析及相关实验设计
  • TiDB删除大量数据需要注意什么
  • RabbitMQ支持的复杂的消息交换模式
  • HTML中滚动加载的实现
  • 大文件上传实现
  • 推理大模型的后训练增强技术-从系统1到系统2:大语言模型推理能力的综述
  • 安卓屏保调试
  • 机试题——Devops 系统任务调度问题
  • 探索具身多模态大模型:开发、数据集和未来方向(下)
  • Node.js系列(1)--架构设计指南
  • Oracle 19c数据库REDO日志更换