MST · 最小生成树里最大的那条边权(瓶颈边)
同样用 Kruskal 建最小生成树,但这次输出 MST 里被选中的边中权重最大的那条的权重(也叫「瓶颈边」)。并查集与排序已给好,补全主循环。
做法:和求总权重一样跑 Kruskal,但用一个变量记录所有被收下的边里最大的 w。
提示:因为边是升序处理的,最后被收下的那条边往往就是最大的;但稳妥起见,每收一条就
if (w > maxw) maxw = w;。 易错点:只在真正被加入 MST(find(u)!=find(v))的边里取最大,别把跳过的环边也算进来。
输入
- 第 1 行:
V E(图连通)。 - 接下来
E行:u v w,无向带权边。
输出
- 一行:MST 中最大的边权。
示例:输入 4 4 / 0 1 1 / 1 2 2 / 2 3 3 / 0 3 4 → 输出 3(MST 选了权 1、2、3,最大是 3)。