Kruskal重构树学习笔记
2021/8/26 23:08:13
本文主要是介绍Kruskal重构树学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法基本概念
\(Kruskal\) 重构树是一种巧妙处理图上边权限制的算法,用某种方法建立出一颗具有特殊性质的树,通过树上的一些操作巧妙处理图上的限制,用起来感觉真的挺妙的,把二者很完美地结合了起来。
主要思想基于 \(kruskal\) 求最小生成树的方法,二者的构建过程是比较相似的,一般地,我们按以下步骤来对一个图构建 \(kruskal\) 重构树。
先按照边权从小到大排序,用并查集维护连通性,若当前的边 \(u->v\) 边权是 \(w\) ,且 \(u,v\) 不属于同一联通块,就新建一个结点 \(cnt\) ,由 \(cnt\) 向 \(u,v\) 当前并查集维护的根节点连一条边,新建的节点作为新的联通块中的根节点,按照这个过程考虑完所有的边之后,得到的就是原图的 \(kruskal\) 重构树了。
以上大概是一些算法概念和定义的介绍,如果读者感觉不知所云或者不知道怎么运用,请继续看下去,下面我们通过一些例题来感受重构树的精妙所在。
里面用到的结论,笔者也会进行一些感性的证明,让读者可以更好地理解。
[LOJ137] 最小瓶颈路 加强版
给定一个 \(n\) 个点 \(m\) 条边的无向连通图,编号为 \(1\) 到 \(n\) ,没有自环,可能有重边,每一条边有一个正权值 \(w\) 。
给出 \(q\) 个询问,每次给出两个不同的点 \(u\) 和 \(v\) ,求一条从 \(u\) 到 \(v\) 的路径上边权的最大值最小是多少。
\(1\le n,m \le 1e5\) , \(1\le q \le 1e7\)
在没有学习本算法之前,一个比较自然的想法是,考虑贪心,开始所有点不连通,我们由小到大对边进行枚举,枚举到一条边后联通它所连接的两个节点,并查集维护一下连通性,枚举到某条边后 \(
这篇关于Kruskal重构树学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程
- 2024-09-26SpringBoot微服务资料入门指南