P1948 [USACO08JAN] Telephone Lines S——有趣的二分答案

· · 个人记录

初见思路

然后可以直接分层跑prim 时间复杂度 $O(nk\log (nk))

还有更好的吗？

发现答案可以二分，于是变成一个可行性问题

贪心地，免 k 次意味着只要 \ge 第 k 大就好

所以说对于答案 ans ，只需要经过边权 > ans 的边 \le k 即可

那么对于每次check，都把一张图的边权变成了 0 和 1 ，考虑 1 到 n 的最短路是否 \le k

时间复杂度 O(n\log V)

二分可以把一个最优性问题变成可行性问题

这样的可行性问题往往可以把原本复杂的权值变成简单的 01

想到了0-1排序原理