当前位置: article > 正文

CodeForces - 1243D 0-1 MST （最小生成树）

作者：数据灵魂 | 2024-02-01 09:36:25

踩

0-1 mst

题面：
在这里插入图片描述
题意：
给定一张n个点的完全图，边权只有0/1两种。
给定完全图中边权为1的边，求一棵最小生成树。

题解：
由于边权为1的边的数量较少，我们可以考虑怎么利用边权为1的边。
因为我们要求最小生成树，那么肯定是要优先选取边权为0的边。
我们把所有能用边权为0的边的连通块搜出来，假设最终有 $c n t$ 个连通块，这些连通块内部均可以用边权为0的边联通，那么最终最小生成树的权值为 $c n t - 1$ 。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
1
2
3
4
5
6
7
8
9
10
11

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/52965