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

LeetCode 3600. 升级后最大生成树稳定性 — Java 实现题目分析核心问题找出一个生成树使其稳定性即树中最小边强度最大化。每条可选边must0最多可升级一次强度翻倍最多使用 k 次升级。关键观察稳定性具有单调性——如果稳定性 x 可行则所有 y x 也可行。因此可以用二分查找并查集解决。解题思路步骤说明预处理将所有必选边must1加入并查集检查是否成环同时记录必选边中最小强度 mn连通性检查将所有边加入并查集若连通分量 1返回 -1二分查找在 [1, mn] 范围内二分答案 limcheck(lim) 先加入所有强度 ≥ lim 的边再用升级次数连接强度 ≥ lim/2 的边升级后翻倍check(lim) 的逻辑1. 将所有 s lim 的边直接加入并查集这些边不升级就能满足要求2. 剩余连通分量需要用升级来连接3. 对于每条可选边若 s * 2 lim升级后能满足则用一次升级加入4. 最多用 k 次升级最终检查是否只剩 1 个连通分量Java 代码javaclass UnionFind {int[] p, size;int cnt;UnionFind(int n) {p new int[n];size new int[n];cnt n;for (int i 0; i n; i) {p[i] i;size[i] 1;}}int find(int x) {if (p[x] ! x) {p[x] find(p[x]);}return p[x];}boolean union(int a, int b) {int pa find(a), pb find(b);if (pa pb) return false;if (size[pa] size[pb]) {p[pb] pa;size[pa] size[pb];} else {p[pa] pb;size[pb] size[pa];}cnt--;return true;}}class Solution {int n;int[][] edges;int k;private boolean check(int lim) {UnionFind uf new UnionFind(n);// Step 1: 直接加入强度 lim 的边不升级for (int[] e : edges) {int u e[0], v e[1], s e[2];if (s lim) {uf.union(u, v);}}// Step 2: 用升级次数连接剩余部分int rem k;for (int[] e : edges) {int u e[0], v e[1], s e[2];// 升级后强度翻倍若翻倍后 lim 则可以用来连接if (s * 2 lim rem 0) {if (uf.union(u, v)) {rem--;}}}return uf.cnt 1;}public int maxStability(int n, int[][] edges, int k) {this.n n;this.edges edges;this.k k;UnionFind uf new UnionFind(n);int mn (int)1e6;// 处理必选边for (int[] e : edges) {int u e[0], v e[1], s e[2], must e[3];if (must 1) {mn Math.min(mn, s);// 必选边成环无法构成生成树if (!uf.union(u, v)) {return -1;}}}// 检查整个图是否连通for (int[] e : edges) {uf.union(e[0], e[1]);}if (uf.cnt 1) {return -1;}// 二分查找最大稳定性int l 1, r mn;while (l r) {int mid (l r 1) 1;if (check(mid)) {l mid;} else {r mid - 1;}}return l;}}复杂度分析指标复杂度时间 O((m \times \alpha(n) n) \times \log M)空间 O(n)其中 m 为边数n 为节点数M 为最大边强度\alpha 为阿克曼函数的反函数并查集近似常数。关键点1. 二分上界 mn必选边中的最小强度是答案的上界因为必选边不能升级生成树稳定性不可能超过最弱的必选边。2. 升级条件 s * 2 lim升级后强度翻倍若翻倍后仍小于 lim则这条边即使升级也无法满足稳定性要求。3. 并查集路径压缩按秩合并保证每次操作接近 O(1)。下载文件: [leetcode_3600.java](sandbox:///mnt/agents/output/leetcode_3600.java)

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

相关推荐

AI协作效率陷阱：多模型协同的挑战与优化

AI提效到底有多少？3个真实项目实测

AI Agent邮箱系统：自动化邮件处理与智能响应实践

更多资讯

Jackett 种子站代理搜索：一个入口搜遍 700 个站，30 秒跑通

ArduPilot飞控系统完整指南：一套代码如何自主驾驭5类无人平台？

SystemInformer完整入门教程：5个实战技巧快速定位Windows资源占用与文件锁定

CesiumJS体素渲染如何实现：从体积数据到实时可视化的完整实践指南

Web端开源ER图工具选型：三款实战推荐

基于MATLAB的MIMO-OFDM仿真程序解析：从发射链路到误码率曲线

今日更新

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

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

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

本周精选

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

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

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

本月热门

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

分布式服务的决策记录

创业产品的首版范围

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