Kimi LeetCode 3600. 升级后最大生成树稳定性 Rust实现

以下是 LeetCode 3600. 升级后最大生成树稳定性Maximize Spanning Tree Stability with Upgrades的 Rust 实现基于二分查找 并查集的解法。ruststruct UnionFind {p: Veci32,sz: Veci32,cnt: i32,}impl UnionFind {fn new(n: i32) - Self {Self {p: (0..n).collect(),sz: vec![1; n as usize],cnt: n,}}fn find(mut self, x: i32) - i32 {let i x as usize;if self.p[i] ! x {self.p[i] self.find(self.p[i]);}self.p[i]}fn union(mut self, a: i32, b: i32) - bool {let (pa, pb) (self.find(a), self.find(b));if pa pb {return false;}let (a, b) (pa as usize, pb as usize);if self.sz[a] self.sz[b] {self.p[a] pb;self.sz[b] self.sz[a];} else {self.p[b] pa;self.sz[a] self.sz[b];}self.cnt - 1;true}}impl Solution {pub fn max_stability(n: i32, edges: VecVeci32, k: i32) - i32 {let mut uf UnionFind::new(n);let mut mn 1_000_000;// 1. 处理必选边for e in edges {if e[3] 1 {mn mn.min(e[2]);if !uf.union(e[0], e[1]) {return -1; // 必选边形成环}}}// 2. 检查图是否连通for e in edges {uf.union(e[0], e[1]);}if uf.cnt 1 {return -1; // 无法连通所有节点}// 3. 二分查找最大稳定性let check |lim: i32| {let mut uf UnionFind::new(n);// 先加入不升级就 lim 的边for e in edges {if e[2] lim {uf.union(e[0], e[1]);}}// 再用升级机会加入升级后 lim 的边let mut rem k;for e in edges {if rem 0 e[2] * 2 lim uf.union(e[0], e[1]) {rem - 1;}}uf.cnt 1};let (mut l, mut r) (1, mn);while l r {let mid (l r 1) 1;if check(mid) {l mid;} else {r mid - 1;}}l}}核心思路1. 二分答案稳定性具有单调性——如果稳定性 x 可行则所有 y x 也可行。因此二分查找最大稳定性。2. check(lim)判断是否能构造出稳定性至少为 lim 的生成树- 不升级即可达先将所有原始强度 s lim 的边加入并查集。- 升级后可达再用最多 k 次升级将满足 s * 2 lim 的边加入每条边最多升一次升级后强度翻倍。3. 边界检查- 必选边must 1若形成环直接返回 -1。- 若所有边都无法使图连通返回 -1。- 答案上界是必选边中的最小强度 mn因为必选边不能升级其最小值决定了生成树稳定性的上限。时间复杂度O((m \cdot \alpha(n) n) \cdot \log M)空间复杂度O(n)。