Kimi LeetCode 3600. 升级后最大生成树稳定性 Python3实现-北京尧图网络

以下是 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)。

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

相关推荐

Codex的goal功能：提升AI编程效率的5段式技巧

Base LLM：从NLP基础到大模型全栈开发实战指南

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

更多资讯

洁净车间环境监控系统设计与实践

Windows全局文件搜索神器Everything：原理、配置与搜索技巧完全指南

CMSIS-6静态工程：嵌入式开发的编译期硬件建模革命

StaffML Vault 大规模构建 Runbook 实战：基于覆盖率分析与 Gemini 迭代生成的题库批量扩充管线

如何使用 supervisord 管理 Appsmith Docker 容器内的后端与 Caddy 进程

PythonRobotics 动态窗口法（Dynamic Window Approach）实现解析：2D 移动机器人局部避障与轨迹规划实战

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？