题解：P11260 [GDKOI2023 普及组] Himitsu

ty_mxzhn · 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)。

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

后记

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

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