风骨散人Chiam
2019.9.18最小生成树知识点总结
关注作者
前往小程序,Get
更优
阅读体验!
立即前往
腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
返回腾讯云官网
风骨散人Chiam
首页
学习
活动
专区
工具
TVP
最新优惠活动
返回腾讯云官网
社区首页
>
专栏
>
2019.9.18最小生成树知识点总结
2019.9.18最小生成树知识点总结
风骨散人Chiam
关注
发布于 2020-10-28 11:08:33
374
0
发布于 2020-10-28 11:08:33
举报
文章被收录于专栏:
CSDN旧文
HDU 4081 Qin Shi Huang's National Road System(次小生成树-Kruskal)
博主的方法很好,但是有疑问,为什么不能将最多人口的两城市的距离设置为0,在进行Prim操作,求B呢?这个将在后续的刷题中体现。
POJ 2377 Bad Cowtractors(最大生成树-Kruskal)
裸题,可以用来熟悉算法。
HDU 6141 I am your Father!(最小树形图)
朱刘算法,这个还不会,稍后来填坑。
CodeForces 609 E.Minimum spanning tree for each edge(最小生成树-Kruskal+在线倍增LCA)
在线倍增LCA,等等再回来填坑
HDU 2121 Ice_cream’s world II(最小树形图)
朱刘算法
HDU 4009 Transfer water(最小树形图)
朱刘算法
POJ 1258 Agri-Net(最小生成树-Prim)
最小生成树裸题!
POJ 3723 Conscription(最小生成树-Kruskal)
这个题是说招募兵,然后亲密关系会减少招募的花费,这个题一开始的思路是并查集,但是后来想,对于因为亲密关系程度不一样,所以还是得用最小生成树,考虑过是不是要枚举节点,后来明白了,不需要根节点,最小生成树生成后根节点也就确定了,所以就没必要了,直接亲密程度设成负值,一遍最小生成树。
POJ 3026 Borg Maze(bfs+最小生成树-Prim)
这个题,是说有一个像史莱姆一样的的怪物,会向四个方向分裂,求分裂的最小次数,也就是说重复的路只算一次,那么我一开始想到的最短路就不对了,因为重复的路径不算,那么也就是说是找的一颗最小生成树,那么需要找到任意两点的距离,但是我看他们只用了一遍BFS,然后搜了搜题解,发现自己看错了,确实是N2遍。
POJ 1789 Truck History(最小生成树-Prim)
最小生成树变形,每个字符串不一样的字符数是距离,然后求最小生成树,字符串判等,暴利即可。
POJ 2485 Highways(最小生成树-Prim)
一遍最小生成树,然后标记最大边输出即可。
本文参与
腾讯云自媒体同步曝光计划
,分享自作者个人站点/博客。
原始发表:2019/09/18 ,如有侵权请联系
cloudcommunity@tencent.com
删除
前往查看
数据分析
编程算法
本文分享自
作者个人站点/博客
前往查看
如有侵权,请联系
cloudcommunity@tencent.com
删除。
本文参与
腾讯云自媒体同步曝光计划
,欢迎热爱写作的你一起参与!
数据分析
编程算法
评论
登录
后参与评论
0 条评论
热度
最新
推荐阅读
LV.
文章
0
获赞
0
领券
问题归档
专栏文章
快讯文章归档
关键词归档
开发者手册归档
开发者手册 Section 归档
0
0
0
推荐