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)
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)
双梁正问题 【 torch 实战】（Python代码实现）)
