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

【蓝桥杯】1124修建公路1（Kruskal算法）

article 2025/3/18 16:57:00

在这里插入图片描述

思路

找到能够连通所有城市的最小树即可，可用Prim或Kruscal。
！！注意，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)