生成树 学习笔记

模板及讲解

最小生成树:在一个图中选择$n-1$条边,使所有点连通且路径总权最小。常用算法是用并查集辅助求解的Kruskal
最小瓶颈路:求一条路径,使得$u−>v$路径上的最大边权最小。可以知道,最小瓶颈路必在最小生成树上,所以用最小生成树求解

最小生成树性质

1切割性质
2回路性质
3相同边权数量相等
4不同边权加入时互相独立
5不产生环的同权值边可以替换边

常见题型

1、求一个图的最小/大生成树
Q:给出一个图,求出这个图的最小/大生成树
解:见讲解
例题:BZOJ 2429
2、将一个图转为树
Q:给出一个图,图中只有使图连通的最大/小的那几条边有用
解:求最小/大生成树。
例题:NOIP2013 D1 T3
3、求一条路径使得最大边最小
Q:给出一个图,求一条路径使得$a->b$最大边最小(这种题的题面一般带有二分的标志:最大值最小)
解:最小瓶颈路。最大边最小的路径在最小生成树上。
例题:BZOJ 2429
4、最小生成树性质
Q:BZOJ 1016
解:BZOJ 1016
例题:BZOJ 1016
5、最小生成树-倍增 (回路性质)
Q:CF 609E
解:CF 609E
例题:CF 609E

------ 本文结束 ------