2594. 稳定通信网

1000ms 512MB 简单
题目描述
某星球上有 `n` 个基地,编号 `1` 到 `n`。现有 `m` 条双向光缆候选线路。第 `i` 条线路连接基地 `u_i` 和 `v_i`,建设费用为 `w_i`,稳定等级为 `s_i`。 现在需要选择恰好 `n-1` 条线路,使得所有基地连通,即形成一棵生成树。 定义这棵生成树的**网络稳定性**为所选边中稳定等级的最小值。 给定预算 `B`,希望在总建设费用不超过 `B` 的前提下,最大化网络稳定性。 如果无论如何都无法在预算内建成连通网络,输出 `-1`。
输入格式
第一行三个整数 `n, m, B`。 接下来 `m` 行,每行四个整数 `u_i, v_i, w_i, s_i`。
输出格式
输出一个整数,表示最大可能的网络稳定性。若无法建成预算内的生成树,输出 `-1`。
样例 1
输入 (Input)

                    
输出 (Output)

                    
样例说明
可以选择以下三条边: - `1-2`,费用 3,稳定等级 5; - `3-4`,费用 2,稳定等级 6; - `1-3`,费用 5,稳定等级 7。 总费用为 $3 + 2 + 5 = 10 <= B$,生成树稳定性为 `min(5,6,7)=5`。 若要求稳定性至少为 6,则只能使用稳定等级 $>=6$的边,无法连通所有基地,因此答案是 5。
- $2 <= n <= 2 \times 10^5$ - $n-1 <= m <= 5 \times 10^5$ - $1 <= u_i, v_i <= n,u_i != v_i$ - $1 <= w_i, s_i <= 10^9$ - $0 <= B <= 10^{18}$ - 图中可能存在重边。
自测终端 stdin → stdout
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout

                
错误 stderr

                
CtrlEnter提交
自动保存已开启
操作成功
wzs_oj@kernel:~ — wzs-sh
guest@wzsoj:~$
刷新页面 F5
复制 Ctrl+C
粘贴 Ctrl+V
搜索题目
训练中心
站点公告
今日神谕
CSP 倒计时
排行榜
我的提交
Esc 关闭 Enter 跳转 支持模糊匹配数字