模拟赛 3

EgLund · 2022-10-19 09:09:20 · 个人记录

T1： 一张不保证连通的图，可以往里加边，到图联通，而且加边权总和为 k。求最大生成树的最大值。加边边权可以不是整数。

贪心策略：连通块内不要加边，除非只有 1 个连通块。

考虑连通块的最大生成树。如果往里加了一条边，

• 它不在新图生成树之中，白加了，浪费边权；
• 它在新图生成树中，一定会替代一条边，答案比不加边要少一个被替代边的边权。

问题：只有 1 个连通块怎么办？加哪条边？

如果这条边比最小边大，那么替代最大生成树中最小边。

如果这条边比最小边小，那么不会影响答案。

赛后补充：假了。。。。。谁告诉我为什么。。。