RainAir
My OI Blog
RainAir
次小生成树

题目链接

题目描述

给定一张图,求出它的严格次小生成树。

解题报告

预备知识:最小生成树最近公共祖先

我们首先来考虑一下严格最小生成树和不严格次小生成树的区别。

首先,对于一个图,可能不只有一个最小生成树。

那么,不严格次小生成树,只需要找出不同于该最小生成树中的生成树中权值最小的那一个,同理,这也有可能有多个。

对于严格次小生成树,必须权值要比最小生成树的权值大。当然也有可能有多个。

先考虑不严格次小生成树怎么做。

不严格次小生成树

首先,一定有一种非常暴力的算法,能求出最小生成树。显而易见:我们先求出MST,然后每次加入一条边,求一遍MST,取最小值即可。

但是这样来看,时间复杂度非常高,每枚举一条边,就需要跑一遍最小生成树。时间复杂度趋近于$ N^2log_2N $。

这个复杂度我们是不能接受的。

那么,我们来看一下算法二。

我们考虑我们每次在最小生成树中加入一条边,这个最小生成树就会变成一个环。怎么让它成为次小呢?首先,”次”已经做到,因为已经加入了一条新的非原最小生成树的边。然后我们需要做到“小”。不难发现,为了使该树的权值尽量的少,我们需要去除一条最大的非新加入的边。

那么,现在就成功的将这个问题转化到了对于一棵树,快速处理出$ (x,y) $点对的路径中的最大权值。

那么,我们可以通过树上动归或LCA或乱搞等,来在$ N^2 $的时间内来处理(当然更优更好)。由于本人太菜,只会LCA。

那么,恭喜您已经掌握了不严格次小生成树的做法了。

严格次小生成树

考虑为什么不严格最小生成树是“不”严格的。

因为它允许权值小于等于的生成树存在。

注意到“等于”,我们不是只需要去掉这个等于就可以了吗?

那么,记录次小值即可。

代码实现

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/78
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

次小生成树
题目链接 题目描述 给定一张图,求出它的严格次小生成树。 解题报告 预备知识:最小生成树,最近公共祖先 我们首先来考虑一下严格最小生成树和不严格次小生成树的区别。 首先,对…
扫描二维码继续阅读
2018-07-13
标签
近期评论