返回题目列表
COMP2521
MST · 最小生成树里的最大边权
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)。
样例
stdin
4 4 0 1 1 1 2 2 2 3 3 0 3 4
期望输出
3
stdin
5 7 0 1 2 0 3 6 1 2 3 1 3 8 1 4 5 2 4 7 3 4 9
期望输出
6
c-dcc
14