目标
给你一个整数 n,表示编号从 0 到 n - 1 的 n 个节点,以及一个 edges 列表,其中 edges[i] = [ui, vi, si, musti]:
- ui 和 vi 表示节点 ui 和 vi 之间的一条无向边。
- si 是该边的强度。
- musti 是一个整数(0 或 1)。如果 musti == 1,则该边 必须 包含在生成树中,且 不能升级 。
你还有一个整数 k,表示你可以执行的最多 升级 次数。每次升级会使边的强度 翻倍 ,且每条可升级边(即 musti == 0)最多只能升级一次。
一个生成树的 稳定性 定义为其中所有边的 最小 强度。
返回任何有效生成树可能达到的 最大 稳定性。如果无法连接所有节点,返回 -1。
注意: 图的一个 生成树(spanning tree)是该图中边的一个子集,它满足以下条件:
- 将所有节点连接在一起(即图是 连通的 )。
- 不 形成任何环。
- 包含 恰好 n - 1 条边,其中 n 是图中节点的数量。
示例 1:
输入: n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1
输出: 2
解释:
边 [0,1] 强度为 2,必须包含在生成树中。
边 [1,2] 是可选的,可以使用一次升级将其强度从 3 提升到 6。
最终的生成树包含这两条边,强度分别为 2 和 6。
生成树中的最小强度是 2,即最大可能稳定性。
示例 2:
输入: n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2
输出: 6
解释:
所有边都是可选的,且最多可以进行 k = 2 次升级。
将边 [0,1] 从 4 升级到 8,将边 [1,2] 从 3 升级到 6。
生成树包含这两条边,强度分别为 8 和 6。
生成树中的最小强度是 6,即最大可能稳定性。
示例 3:
输入: n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0
输出: -1
解释:
所有边都是必选的,构成了一个环,这违反了生成树无环的性质。因此返回 -1。
说明:
- 2 <= n <= 10^5
- 1 <= edges.length <= 10^5
- edges[i] = [ui, vi, si, musti]
- 0 <= ui, vi < n
- ui != vi
- 1 <= si <= 10^5
- musti 是 0 或 1。
- 0 <= k <= n
- 没有重复的边。
思路
// todo
代码