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
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功