OlveraeUNSW
返回题目列表
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