1. 最小生成树裸题
AcWing 1140. 最短网络
AcWing 1141. 局域网
2. 最小生成树且任意两点间最大的边权最小
依旧是Kruskal直接做
AcWing 1142. 繁忙的都市
AcWing 1145. 北极通讯网络
J-最短路
3. 部分边必选的最小生成树
将必选的边联通的所有点看作一个点即可，类似Prim的考虑方式
AcWing 1143. 联络员
AcWing 1144. 连接格点
4. 最小生成树结合虚拟源点
既有边权，又有点权，建立超级源点，将点权转换成边权，将最小生成森林转换成最小生成树。
AcWing 1146. 新的开始
5. 树扩充为完全图
Kruskal算法的扩展，按边权排序然后累加
AcWing 346. 走廊泼水节
6. 次小生成树
- 求最小生成树，标记每一条边是树边还是非树边；同时建好最小生成树
- 预处理任意两点间的边权最大值和次大值
d1[a][b], d2[a][b] - 依次枚举所有非树边，求
min(sum + w - d[a][b]), w > d[a][b]
这样能求出严格次小生成树。如果要求非严格次小生成树，则不需要满足w > d[a][b]，直接替换d1[a][b]即可
若有收获，就点个赞吧
0 人点赞
