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

以下是 LeetCode 3600. 升级后最大生成树稳定性Maximize Spanning Tree Stability with Upgrades的 C 实现基于二分查找 并查集的解法。cppclass UnionFind {public:vectorint p, sz;int cnt;UnionFind(int n) {p.resize(n);sz.resize(n, 1);cnt n;iota(p.begin(), p.end(), 0);}int find(int x) {if (p[x] ! x) {p[x] find(p[x]);}return p[x];}bool unite(int a, int b) {int pa find(a), pb find(b);if (pa pb) return false;if (sz[pa] sz[pb]) {p[pa] pb;sz[pb] sz[pa];} else {p[pb] pa;sz[pa] sz[pb];}--cnt;return true;}};class Solution {public:int maxStability(int n, vectorvectorint edges, int k) {// 1. 处理必选边UnionFind uf(n);int mn 1e6;for (auto e : edges) {if (e[3] 1) {mn min(mn, e[2]);if (!uf.unite(e[0], e[1])) {return -1; // 必选边形成环}}}// 2. 检查图是否连通for (auto e : edges) {uf.unite(e[0], e[1]);}if (uf.cnt 1) {return -1; // 无法连通所有节点}// 3. 二分查找最大稳定性auto check [](int lim) - bool {UnionFind uf2(n);// 先加入不升级就 lim 的边for (auto e : edges) {if (e[2] lim) {uf2.unite(e[0], e[1]);}}// 再用升级机会加入升级后 lim 的边int rem k;for (auto e : edges) {if (rem 0 e[2] * 2 lim uf2.unite(e[0], e[1])) {--rem;}}return uf2.cnt 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;}};核心思路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)。