最小生成树

AC_zzh2013 · 2025-04-14 20:37:20 · 个人记录

最小生成树(Mini,al Spanning Tree,MST)

定义

在一条无向图G中，有几个点和m条边，连接n个点形成的树形结构，称之为G的最小生成树。

实现方法

方法1：kruskal算法，以边为研究对象，适用于稀疏图。

方法2：prim算法，以点为研究对象，适用于稠密图。

kruskal算法：

算法思想：贪心思想

1.优先使用边权小的边，因此边可以按边权从小到大排序。

2.如果1条边不能连通新的点，那么这条边不用。

代码实现

1.将输入的边排序。

2.并查集初始化。

3.枚举m条边，对于第i条边：

if(find(e[i].x)==find(e[i].y))
    continue;
unionn(e[i].x,e[i].y);
ans+=e[i].w;

时间复杂度：O(mlog_mm)

第一个类型：模版题，P3366 【模板】最小生成树

1.给出n个点，m条边。

2.告诉我们每条边的边权，找最小生成树。

分析：

1.按题目建图。

2.跑kruskal最小生成树

第二个类型：枚举建边，P1991 无线通讯网

1.给定p个点，s个卫星电话。

2.卫星电话之间免费，且无视距离。

3.无线电以通话距离为费用。

求：p个点的最小费用。

分析

1.p个点连接需要p-1条边。

2.s个卫星电话可以连接s-1条边。

3.无线电还需要连边数=(p-1)-(s-1)=p-s。

4.p个哨所双重循环建边，距离为平面距离。

5.选取不成环的第p-s条边的边权即为答案。

第三个类型：虚拟点位，P1550 [USACO08OCT] Watering Hole G

1.图中既有点权又有边权，考虑统一。

2.虚拟一个点，编号为n+1，代表所以打井的水都从n+1来。

3.1到n的每个店向n=1连边，边权为w[i]。

4.对n+1个点的新图跑kruskal即可。