自动搬运

查看原文

来自洛谷，原作者为

	ty_mxzhn 打破天生的劣等感 || 写作悔恨的未来

搬运于2025-08-24 23:05:49，当前版本为作者最后更新于2024-12-16 20:05:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

你有一个图，你要求它在选出 $i(0\le i\le k)$ 条关键边时的最小生成树。保证非关键边能连通这个图。

题解

算法 $1$

答案显然是凸的，考虑 wqs 二分直接跑最小生成树。时间复杂度 $O(mk\log V)$。无法通过。

算法 $2$

怎么求 $i=0$ 时的答案？考虑将其他非关键边缩成一棵最小生成树。此时不在最小生成树上的边没有用。缩成 $n+k$ 条边了。

结合算法 $1$ 则时间复杂度 $O(nk\log V)$。可以通过。

算法 $3$

整体二分（或分治，怎么叫都行），对于 $i\in[L,R]$ 的区间对切的斜率二分到 $[l,r]$ 这个区间。

设 $m=\lfloor \dfrac{l+r}{2} \rfloor$。判定到 $m$ 时我们的二分加了 $M$ 条关键边。则每次被二分扔到 $[l,m]$ 这个区间的数是 $i\in [L,M]$，被二分扔到 $[m+1,r]$ 这个区间的数是 $i\in [M+1,R]$。

这个算法的时间复杂度是什么？好像有点难分析吧。

考虑画出二分的递归树，发现时间复杂度为 $O(nk)$。

我们发现时间复杂度相对于原来没有太大变化。正常整体二分的时间复杂度进行较大改变是因为值域较小且每一段的二分时间复杂度只和这一段的长度有关。

后记

秘密啊 总是会有那么一个两个的

因为人类啊 其实也没有多坚强