首页 > [SCOI2005]繁忙的都市
开通博客写题解
头像 威风镰鼬
发表于 2021-07-29 14:32:32
思路 最小生成树的板子题，前置知识：并查集以及Kruskal算法；答案要求输出最小生成树的边数（那肯定是n-1啊）以及最大权值的边（那肯定是最后连的那一条啊）因为做过最小生成树的课件，代码注释解释了很多，大家可以看看。 代码 #include<bits/stdc++.h> using n 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 an_da
发表于 2021-05-17 13:14:48
思路：1.先存储所有的边，包括起点，终点，权值u,v,w2.对所有的边按权值从小到大排序3.最小生成树得到的边数一定是n-1（点的数目减一），按权值从小到大取边，如果选中该边，就把这条边的两个点加入到一个集合（表示有同样的归属关系，就是我们所说的并查集）里面，下次选边时，如果有节点已经在这个集合中， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”