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邮箱系统：自动化邮件处理与智能响应实践

更多资讯

安监局电工证考试流程全流程办理指南多久拿证

办理办电工证需多少钱需要什么材料

安监局电工证考试流程在哪考外省证书能否转过来

诸暨考电工证上哪通过率揭秘：转岗电工怎么高效取证

广西电工证理论考什么内部消息来了！找工作必须知道的细节

电工作业危险有害因素怎么避坑？全国通用证书这样考

今日更新

高压电工证哪里可以挂多久拿证全攻略：实操考试心里没底怕挂科别慌

电工证的理论题目在哪考，外省证怎么转过来

工地太忙根本没时间复习考试，职业学校的电工证值不值得考？

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

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