威风镰鼬

题解

/ 注册

全部文章 / 题解（共3篇）

题解 | #[SCOI2005]繁忙的都市#

思路最小生成树的板子题，前置知识：并查集以及Kruskal算法；答案要求输出最小生成树的边数（那肯定是n-1啊）以及最大权值的边（那肯定是最后连的那一条啊）因为做过最小生成树的课件，代码注释解释了很多，大家可以看看。代码 #include<bits/stdc++.h> using n...

最小生成树 Kruskal 并查集

2021-07-29

1 489

题解 | #挖沟#

思路与<15108道路建设>同解，Kruskal硬过就行了。代码 #include<bits/stdc++.h> using namespace std; const int maxn=100005,maxm=1000005; struct E{ int fro...

普及组最短路 Kruskal 图论

2021-06-12

1 477

题解 | #道路建设#

思路最小生成树板子题，用Kruskal硬过就行了。算法流程：初始设点在集合A，无连边；将图中的边按照权值从小到大排序，然后从最小的边开始连接（使用并查集）；将边的两端点加入集合B，如果当前边的两个端点不都在集合A，则进行连接；选择m-1条边的时候刚好将m个点连上，此时判断权值之和是否大于c。代码...

最小生成树 Kruskal NOIP

2021-06-12

1 430