[最小生成树] CF76A

_Cheems · 2024-01-31 20:46:42 · 个人记录

无法直接做，考虑枚举 \max g 那么只要求出 g_i\le \max g 的边所构成的图上、以 s 维为边权的最小生成树即可。

（最小生成树 = 最小瓶颈生成树）。

将边按照 g 排序，则问题变为逐次加入边，求每次加入后最小生成树？

假设取新加入的边，则必须在该边于原生成树上形成的环上删去一边，才可得到新的生成树。那么只需证明删去的边对之后的答案没有影响，就可按照上述过程求解了。

考虑 krsukal 的过程，易发现该边被删去，等价于在此之前 u_i,v_i 属于同一连通块，由于此后边只增不减，所以之后遍历到该边时依然满足它们在同一连通块。

然后乱搞就好啦。。。