CSP 201703-4 地铁修建 python 最小生成树,并查集

简介: CSP 201703-4 地铁修建 python 最小生成树,并查集

CSP 201703-4 地铁修建 python 最小生成树,并查集


题目描述


0f7fc59b92aa4111ad4a74af3508898e.png

样例输入
6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6
样例输出
6

思路


  • 由于所有的隧道同时开始修建,则当需要花费时间最长的隧道的时间值最小时,即为修建整条地铁线路最少的时间。
  • 采用最小生成树思想,运用Kruskal算法即可求解。
  • 采用并查集思想,当第一个点和最后一个点在同一个集合时,表明此时隧道已经修建 完毕,输出最后完成的隧道所需天数即可。


代码

# http://118.190.20.162/view.page?gpid=T54
# 并查集 + Kruskal算法
n,m = map(int,input().split())
w = []
for i in range(m):
    a,b,c = map(int,input().split())
    w.append((a,b,c))
f = [i for i in range(n+1)]
def get_father(x):
    if f[x] != x:
        f[x] = get_father(f[x])
    return f[x]
def union(x,y):
    fx,fy = get_father(x),get_father(y)
    if fx != fy:
        f[fy] = fx
# 排序
w.sort(key = lambda x:x[2])
# 构建最小生成树0
for i in w:
    u,v,w = i
    if get_father(u) != get_father(v):
        union(u,v)
        if get_father(1) == get_father(n):
            print(w)
            break


相关文章
|
4月前
|
算法 开发者 计算机视觉
燃爆全场!Python并查集:数据结构界的网红,让你的代码炫酷无比!
在编程的世界里,总有一些数据结构以其独特的魅力和高效的性能脱颖而出,成为众多开发者追捧的“网红”。今天,我们要介绍的这位明星,就是Python中的并查集(Union-Find)——它不仅在解决特定问题上大放异彩,更以其优雅的设计和强大的功能,让你的代码炫酷无比,燃爆全场!
55 0
|
4月前
|
Python
智慧之光!Python并查集:点亮你的编程思维,让复杂问题迎刃而解!
并查集以其简洁而强大的功能,成为了解决特定类型问题的首选工具。在编程的旅途中,掌握并查集不仅能帮助我们解决眼前的难题,更能点亮我们的编程思维,让我们在面对更复杂的问题时也能游刃有余。希望今天的分享能激发你对并查集的兴趣,让你在未来的编程道路上走得更远、更稳。
44 1
|
4月前
|
存储 算法 Python
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
54 1
|
5月前
|
Python
逆天改命!掌握Python并查集,数据结构难题从此不再是你的痛!
在编程旅程中,遇到棘手的数据结构难题是否让你苦恼?别担心,Python并查集(Union-Find)是你的得力助手。这是一种高效处理不相交集合合并及查询的数据结构,广泛应用于网络连通性、社交网络圈子划分等场景。通过维护每个集合的根节点,它实现了快速合并与查询。本文将介绍并查集的基本概念、应用场景以及如何在Python中轻松实现并查集,帮助你轻松应对各种数据结构挑战。
47 3
|
5月前
|
数据采集 JSON 数据格式
Python:南京地铁每日客流数据的爬虫实现
Python:南京地铁每日客流数据的爬虫实现
98 1
|
5月前
|
算法 计算机视觉 Python
Python并查集大揭秘:让你在算法界呼风唤雨,秒杀一切复杂场景!
在编程与算法的广袤天地中,总有一些工具如同神兵利器,能够助你一臂之力,在复杂的问题前游刃有余。今天,我们就来深入探讨这样一件神器——Python并查集(Union-Find),看看它是如何让你在算法界呼风唤雨,轻松应对各种复杂场景的。
94 2
|
5月前
|
Python
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
42 0
|
5月前
|
算法 开发者 计算机视觉
Python并查集:数据结构界的肌肉男,让你在编程路上无所畏惧!
在编程的浩瀚宇宙中,数据结构如同基石,构建了解决问题的坚实框架。而并查集(Union-Find),这位数据结构界的“肌肉男”,以其独特的魅力和强大的功能,让无数开发者在面对复杂关系处理时,都能感受到前所未有的从容与自信。今天,就让我们一同揭开并查集的神秘面纱,看看它是如何成为你编程路上的得力助手的。
44 0
|
5月前
|
算法 程序员 计算机视觉
Python并查集:数据结构界的肌肉男,让你在编程路上无所畏惧!
并查集,一种处理不相交集合合并与查询的数据结构,被誉为编程的“肌肉男”。它提供Find(找根节点)和Union(合并集合)操作,常用于好友关系判断、图像处理、集合合并等。Python实现中,路径压缩和按秩合并优化效率。并查集的高效性能使其成为解决问题的强大工具,助力程序员应对复杂挑战。
44 0
|
7月前
|
算法 程序员 图形学
脑洞大开!Python并查集:用最简单的方式,解决最复杂的数据结构问题!
【7月更文挑战第17天】并查集,数据结构明星,处理不相交集合合并与查询。Python实现核心操作:查找与合并。路径压缩优化查找,按秩合并保持平衡。实战应用如图连通性判断,算法竞赛利器。掌握并查集,解锁复杂问题简单解法,照亮编程之旅!
74 10