3600.升级后最大生成树稳定性

目标

给你一个整数 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

代码

性能