【蓝桥杯】1124修建公路1(Kruskal算法)
思路
找到能够连通所有城市的最小树即可,可用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)