AvariceZhao
AvariceZhao
全部文章
分类
题解(3)
归档
标签
去牛客网
登录
/
注册
AvariceZhao的博客
全部文章
(共2篇)
题解 | #Forsaken喜欢独一无二的树#
题意 删除一些边,使得最小生成树唯一,问删除的边的权值和最小是多少? 思路 kruskal按边权从小到大排序后可以视为将所有边按边权分段,在同一段内先将可能的边全部计入,随后遍历这一段长度相同的边,对于左右端点不在同一集合里的边将边权从累加的边权和删去,即保留一条最小生成树中的边。剩余的即为应删去的...
最小生成树
2022-07-09
0
349
[HNOI2006]公路修建问题
最小生成树、kruskai算法 题意: 废话:做了些题单的题后,我发现题目考察点基本上围绕着 建图、算法本身理解、dp 三点展开。本题考察的是对kruskai算法的理解 分析: 我们首先抓住重要信息:公路1是一定比公路2开销大的!至少要有k条公路1.那么很明显我们就只铺设k条公路1好了,剩下的都...
最小生成树
2020-07-29
1
644