2025-12-12：升级后最大生成树稳定性。用go语言，给出一个包含编号 0 到 n-1 的 n 个节点的无向图，边的列表 edges 中每条记录为 [ui, vi, si, musti]，含义如下：

• ui、vi：该条边连接的两个端点（无向）。

• si：这条边的“强度”值。

• musti：若为 1，则该边是“必选”的——在最后的边集合中必须包含，且不能进行升级；若为 0，则该边可以考虑升级（但最多升级一次）。

你还有一个整数 k，表示最多可以对不为 must 的边执行 k 次升级操作。每次升级把该边的强度翻倍，且每条可升级的边最多只能升级一次。

把一组边选成使图连通且不含环、边数恰好为 n−1 的集合（即把所有节点连成一棵），称为一个生成树。一个生成树的稳定性定义为其所含边强度的最小值。

问题要求：在不超过 k 次总升级、且所有 musti=1 的边必须被选入（且不能升级）的前提下，找出任意一棵合法生成树可以达到的最大稳定性；若不存在任何能把所有节点连通的合法生成树，则返回 -1。

2 <= n <= 100000。

1 <= edges.length <= 100000。

edges[i] = [ui, vi, si, musti]。

0 <= ui, vi < n。

ui != vi。

1 <= si <= 100000。

musti 是 0 或 1。

0 <= k <= n。

没有重复的边。

输入： n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2。

输出： 6。

解释：

所有边都是可选的，且最多可以进行 k = 2 次升级。

将边 [0,1] 从 4 升级到 8，将边 [1,2] 从 3 升级到 6。

生成树包含这两条边，强度分别为 8 和 6。

生成树中的最小强度是 6，即最大可能稳定性。

题目来自力扣3600。

🛠️ 解题步骤详解

步骤1：初始化并查集

算法使用两个并查集（Union-Find）数据结构：

• uf：用于构建包含所有必选边的连通分量，并在此基础上尝试添加可选边以形成生成树。
• allUf：用于快速检查整个图是否连通。它会合并所有边（包括必选和可选），如果最终连通块数量大于1，则说明图本身不连通，直接返回-1。

步骤2：处理必选边

遍历所有边，对于标记为 musti = 1 的必选边：

• 尝试将其加入 uf。如果加入这条边导致环的出现（即边的两个端点已经在同一个连通分量中），则说明必选边自身存在环，无法形成树结构，立即返回 -1。
• 同时，记录所有必选边中的最小强度值 minS1。在最终的生成树中，稳定性（即最小边权）不会超过这个值，因为必选边不能被升级。

步骤3：连通性检查

使用 allUf 检查整个图的连通性。如果图不连通，则不可能形成生成树，直接返回 -1。

步骤4：判断所需可选边数量

设 left = uf.cc - 1。这个值表示在合并了所有必选边之后，还需要多少条可选边才能将剩余的连通块连接成一棵树（生成树的边数总为 n-1）。

• 如果 left == 0，说明仅凭必选边就已经构成了生成树。此时，生成树的稳定性就是必选边中的最小强度 minS1，直接返回该值。

步骤5：使用Kruskal算法构建最大生成树

如果还需要添加可选边，则采用类似Kruskal最大生成树算法的策略：

1. 排序：将所有边按强度值从大到小排序。这样能优先考虑强度高的边，有助于提高最终生成树的稳定性。
2. 选边：遍历排序后的边列表，对于每条可选边（musti = 0）：
   • 如果加入该边不会在 uf 中形成环，则将其加入生成树。
   • 根据当前已使用的可选边数量与剩余升级次数 k 的关系，更新答案 ans：
     • 如果已选的可选边数量 <= k，意味着这些边都可以被升级一次。此时，生成树的稳定性由这些边升级后的最小强度值决定，即 min(ans, s*2)。
     • 如果已选的可选边数量 > k，那么只有部分边能被升级。为了保证稳定性最大，我们会升级强度最高的k条边，因此生成树的稳定性由未被升级的边中最小的原始强度值决定，即 min(ans, s)。
3. 终止条件：当加入的可选边数量达到 left 时，生成树构建完成，退出循环。

⏱️ 复杂度分析

时间复杂度

• 排序操作：对边列表进行排序，时间复杂度为 O(m log m)，其中 m 是边的数量。这是算法的主要时间开销。
• 并查集操作：包括初始化和多次合并、查找操作。使用了路径压缩优化，单次操作的平均时间复杂度接近常数 O(α(n))，其中 α(n) 是反阿克曼函数。整个过程的操作次数是 O(m) 级别，因此并查集部分的总时间复杂度约为 O(m α(n))。
• 综合：总时间复杂度由排序操作主导，为 O(m log m)。

空间复杂度

• 存储边：需要 O(m) 的空间来存储边的信息。
• 并查集数据结构：需要 O(n) 的空间存储父节点等信息。
• 综合：总的额外空间复杂度为 O(m + n)。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
	"slices"
)

type unionFind struct {
	fa []int // 代表元
	cc int   // 连通块个数
}

func newUnionFind(n int) unionFind {
	fa := make([]int, n)
	// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
	// 集合 i 的代表元是自己
	for i := range fa {
		fa[i] = i
	}
	return unionFind{fa, n}
}

// 返回 x 所在集合的代表元
// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
func (u unionFind) find(x int) int {
	// 如果 fa[x] == x，则表示 x 是代表元
	if u.fa[x] != x {
		u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
	}
	return u.fa[x]
}

// 把 from 所在集合合并到 to 所在集合中
// 返回是否合并成功
func (u *unionFind) merge(from, to int) bool {
	x, y := u.find(from), u.find(to)
	if x == y { // from 和 to 在同一个集合，不做合并
		return false
	}
	u.fa[x] = y // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
	u.cc--      // 成功合并，连通块个数减一
	return true
}

func maxStability(n int, edges [][]int, k int) int {
	uf := newUnionFind(n)
	allUf := newUnionFind(n)
	minS1 := math.MaxInt
	for _, e := range edges {
		x, y, s, must := e[0], e[1], e[2], e[3]
		if must > 0 {
			if !uf.merge(x, y) { // 必选边成环
				return -1
			}
			minS1 = min(minS1, s)
		}
		allUf.merge(x, y)
	}

	if allUf.cc > 1 { // 图不连通
		return -1
	}

	left := uf.cc - 1
	if left == 0 { // 只需选必选边
		return minS1
	}

	ans := minS1
	// Kruskal 算法求最大生成树
	slices.SortFunc(edges, func(a, b []int) int { return b[2] - a[2] })
	for _, e := range edges {
		x, y, s, must := e[0], e[1], e[2], e[3]
		if must == 0 && uf.merge(x, y) {
			if left > k {
				ans = min(ans, s)
			} else {
				ans = min(ans, s*2)
			}
			left--
			if left == 0 { // 已经得到生成树了
				break
			}
		}
	}
	return ans
}

func main() {
	n := 3
	edges := [][]int{{0, 1, 4, 0}, {1, 2, 3, 0}, {0, 2, 1, 0}}
	k := 2
	result := maxStability(n, edges, k)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math

class UnionFind:
    def __init__(self, n: int):
        self.fa = list(range(n))  # 代表元
        self.cc = n               # 连通块个数
    
    def find(self, x: int) -> int:
        """返回 x 所在集合的代表元，同时做路径压缩"""
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    
    def merge(self, from_: int, to: int) -> bool:
        """把 from 所在集合合并到 to 所在集合中，返回是否合并成功"""
        x, y = self.find(from_), self.find(to)
        if x == y:
            return False
        self.fa[x] = y
        self.cc -= 1
        return True

def max_stability(n: int, edges: list[list[int]], k: int) -> int:
    uf = UnionFind(n)
    all_uf = UnionFind(n)
    min_s1 = math.inf
    
    # 处理必选边
    for e in edges:
        x, y, s, must = e
        if must > 0:
            if not uf.merge(x, y):  # 必选边成环
                return -1
            min_s1 = min(min_s1, s)
        all_uf.merge(x, y)
    
    # 检查图的连通性
    if all_uf.cc > 1:
        return -1
    
    left = uf.cc - 1  # 还需连接的连通块数
    if left == 0:      # 只需选必选边
        return min_s1
    
    ans = min_s1
    
    # Kruskal 算法求最大生成树（按稳定度降序排序）
    edges.sort(key=lambda e: -e[2])
    for e in edges:
        x, y, s, must = e
        if must == 0 and uf.merge(x, y):
            if left > k:
                ans = min(ans, s)
            else:
                ans = min(ans, s * 2)
            left -= 1
            if left == 0:  # 已经得到生成树
                break
    
    return ans

if __name__ == "__main__":
    n = 3
    edges = [[0, 1, 4, 0], [1, 2, 3, 0], [0, 2, 1, 0]]
    k = 2
    result = max_stability(n, edges, k)
    print(result)  # 输出: 6

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class UnionFind {
private:
    vector<int> fa; // 代表元
    int cc;         // 连通块个数

public:
    // 构造函数，初始化n个独立集合
    UnionFind(int n) : cc(n) {
        fa.resize(n);
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，把 x 所在集合中的所有元素的 fa 都改成代表元
    int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 把 from 所在集合合并到 to 所在集合中
    // 返回是否合并成功
    bool merge(int from, int to) {
        int x = find(from);
        int y = find(to);
        if (x == y) { // from 和 to 在同一个集合，不做合并
            return false;
        }
        fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        cc--;      // 成功合并，连通块个数减一
        return true;
    }

    // 获取连通块个数
    int getCC() const {
        return cc;
    }
};

int maxStability(int n, vector<vector<int>>& edges, int k) {
    UnionFind uf(n);
    UnionFind allUf(n);
    int minS1 = INT_MAX;

    // 处理必选边
    for (const auto& e : edges) {
        int x = e[0], y = e[1], s = e[2], must = e[3];
        if (must > 0) {
            if (!uf.merge(x, y)) { // 必选边成环
                return -1;
            }
            minS1 = min(minS1, s);
        }
        allUf.merge(x, y);
    }

    // 检查图的连通性
    if (allUf.getCC() > 1) { // 图不连通
        return -1;
    }

    // 计算还需选择的边数
    int left = uf.getCC() - 1;
    if (left == 0) { // 只需选必选边
        return minS1;
    }

    int ans = minS1;

    // 按边权从大到小排序（Kruskal求最大生成树）
    sort(edges.begin(), edges.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[2] > b[2]; // 按稳定性值降序排序
         });

    // Kruskal算法选择边
    for (const auto& e : edges) {
        int x = e[0], y = e[1], s = e[2], must = e[3];
        if (must == 0 && uf.merge(x, y)) {
            if (left > k) {
                ans = min(ans, s);
            } else {
                ans = min(ans, s * 2);
            }
            left--;
            if (left == 0) { // 已经得到生成树了
                break;
            }
        }
    }

    return ans;
}

int main() {
    int n = 3;
    vector<vector<int>> edges = {{0, 1, 4, 0}, {1, 2, 3, 0}, {0, 2, 1, 0}};
    int k = 2;
    int result = maxStability(n, edges, k);
    cout << result << endl; // 输出结果

    return 0;
}