以下是 LeetCode 3600. 升级后最大生成树稳定性Maximize Spanning Tree Stability with Upgrades的 Python3 实现基于二分查找 并查集的解法。pythonfrom typing import Listclass UnionFind:def __init__(self, n):self.p list(range(n))self.size [1] * nself.cnt ndef find(self, x):if self.p[x] ! x:self.p[x] self.find(self.p[x])return self.p[x]def union(self, a, b):pa, pb self.find(a), self.find(b)if pa pb:return Falseif self.size[pa] self.size[pb]:self.p[pb] paself.size[pa] self.size[pb]else:self.p[pa] pbself.size[pb] self.size[pa]self.cnt - 1return Trueclass Solution:def maxStability(self, n: int, edges: List[List[int]], k: int) - int:def check(lim: int) - bool:uf UnionFind(n)# 第一阶段先加入所有不升级就 lim 的边for u, v, s, _ in edges:if s lim:uf.union(u, v)# 第二阶段用升级次数加入升级后 lim 的边rem kfor u, v, s, _ in edges:if s * 2 lim and rem 0:if uf.union(u, v):rem - 1return uf.cnt 1# 预处理检查必选边uf UnionFind(n)mn 10**6for u, v, s, must in edges:if must:mn min(mn, s)if not uf.union(u, v):return -1 # 必选边形成环# 检查图是否连通for u, v, _, _ in edges:uf.union(u, v)if uf.cnt 1:return -1 # 无法连通所有节点# 二分查找最大稳定性范围 [1, mn]# mn 是必选边中的最小强度答案不可能超过它l, r 1, mnwhile l r:mid (l r 1) 1if check(mid):l midelse:r mid - 1return 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)。
以下是 LeetCode 3600. 升级后最大生成树稳定性Maximize Spanning Tree Stability with Upgrades的 Python3 实现基于二分查找 并查集的解法。pythonfrom typing import Listclass UnionFind:def __init__(self, n):self.p list(range(n))self.size [1] * nself.cnt ndef find(self, x):if self.p[x] ! x:self.p[x] self.find(self.p[x])return self.p[x]def union(self, a, b):pa, pb self.find(a), self.find(b)if pa pb:return Falseif self.size[pa] self.size[pb]:self.p[pb] paself.size[pa] self.size[pb]else:self.p[pa] pbself.size[pb] self.size[pa]self.cnt - 1return Trueclass Solution:def maxStability(self, n: int, edges: List[List[int]], k: int) - int:def check(lim: int) - bool:uf UnionFind(n)# 第一阶段先加入所有不升级就 lim 的边for u, v, s, _ in edges:if s lim:uf.union(u, v)# 第二阶段用升级次数加入升级后 lim 的边rem kfor u, v, s, _ in edges:if s * 2 lim and rem 0:if uf.union(u, v):rem - 1return uf.cnt 1# 预处理检查必选边uf UnionFind(n)mn 10**6for u, v, s, must in edges:if must:mn min(mn, s)if not uf.union(u, v):return -1 # 必选边形成环# 检查图是否连通for u, v, _, _ in edges:uf.union(u, v)if uf.cnt 1:return -1 # 无法连通所有节点# 二分查找最大稳定性范围 [1, mn]# mn 是必选边中的最小强度答案不可能超过它l, r 1, mnwhile l r:mid (l r 1) 1if check(mid):l midelse:r mid - 1return 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)。
双梁正问题 【 torch 实战】（Python代码实现）)
