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

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最大生成树算法的策略：

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

packagemainimport("fmt""math""slices")typeunionFindstruct{fa[]int// 代表元ccint// 连通块个数}funcnewUnionFind(nint)unionFind{fa:=make([]int,n)// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己fori:=rangefa{fa[i]=i}returnunionFind{fa,n}}// 返回 x 所在集合的代表元// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元func(u unionFind)find(xint)int{// 如果 fa[x] == x，则表示 x 是代表元ifu.fa[x]!=x{u.fa[x]=u.find(u.fa[x])// fa 改成代表元}returnu.fa[x]}// 把 from 所在集合合并到 to 所在集合中// 返回是否合并成功func(u*unionFind)merge(from,toint)bool{x,y:=u.find(from),u.find(to)ifx==y{// from 和 to 在同一个集合，不做合并returnfalse}u.fa[x]=y// 合并集合。修改后就可以认为 from 和 to 在同一个集合了u.cc--// 成功合并，连通块个数减一returntrue}funcmaxStability(nint,edges[][]int,kint)int{uf:=newUnionFind(n)allUf:=newUnionFind(n)minS1:=math.MaxIntfor_,e:=rangeedges{x,y,s,must:=e[0],e[1],e[2],e[3]ifmust>0{if!uf.merge(x,y){// 必选边成环return-1}minS1=min(minS1,s)}allUf.merge(x,y)}ifallUf.cc>1{// 图不连通return-1}left:=uf.cc-1ifleft==0{// 只需选必选边returnminS1}ans:=minS1// Kruskal 算法求最大生成树slices.SortFunc(edges,func(a,b[]int)int{returnb[2]-a[2]})for_,e:=rangeedges{x,y,s,must:=e[0],e[1],e[2],e[3]ifmust==0&&uf.merge(x,y){ifleft>k{ans=min(ans,s)}else{ans=min(ans,s*2)}left--ifleft==0{// 已经得到生成树了break}}}returnans}funcmain(){n:=3edges:=[][]int{{0,1,4,0},{1,2,3,0},{0,2,1,0}}k:=2result:=maxStability(n,edges,k)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-importmathclassUnionFind:def__init__(self,n:int):self.fa=list(range(n))# 代表元self.cc=n# 连通块个数deffind(self,x:int)->int:"""返回 x 所在集合的代表元，同时做路径压缩"""ifself.fa[x]!=x:self.fa[x]=self.find(self.fa[x])returnself.fa[x]defmerge(self,from_:int,to:int)->bool:"""把 from 所在集合合并到 to 所在集合中，返回是否合并成功"""x,y=self.find(from_),self.find(to)ifx==y:returnFalseself.fa[x]=y self.cc-=1returnTruedefmax_stability(n:int,edges:list[list[int]],k:int)->int:uf=UnionFind(n)all_uf=UnionFind(n)min_s1=math.inf# 处理必选边foreinedges:x,y,s,must=eifmust>0:ifnotuf.merge(x,y):# 必选边成环return-1min_s1=min(min_s1,s)all_uf.merge(x,y)# 检查图的连通性ifall_uf.cc>1:return-1left=uf.cc-1# 还需连接的连通块数ifleft==0:# 只需选必选边returnmin_s1 ans=min_s1# Kruskal 算法求最大生成树（按稳定度降序排序）edges.sort(key=lambdae:-e[2])foreinedges:x,y,s,must=eifmust==0anduf.merge(x,y):ifleft>k:ans=min(ans,s)else:ans=min(ans,s*2)left-=1ifleft==0:# 已经得到生成树breakreturnansif__name__=="__main__":n=3edges=[[0,1,4,0],[1,2,3,0],[0,2,1,0]]k=2result=max_stability(n,edges,k)print(result)# 输出: 6

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<climits>usingnamespacestd;classUnionFind{private:vector<int>fa;// 代表元intcc;// 连通块个数public:// 构造函数，初始化n个独立集合UnionFind(intn):cc(n){fa.resize(n);// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己for(inti=0;i<n;i++){fa[i]=i;}}// 返回 x 所在集合的代表元// 同时做路径压缩，把 x 所在集合中的所有元素的 fa 都改成代表元intfind(intx){// 如果 fa[x] == x，则表示 x 是代表元if(fa[x]!=x){fa[x]=find(fa[x]);// fa 改成代表元}returnfa[x];}// 把 from 所在集合合并到 to 所在集合中// 返回是否合并成功boolmerge(intfrom,intto){intx=find(from);inty=find(to);if(x==y){// from 和 to 在同一个集合，不做合并returnfalse;}fa[x]=y;// 合并集合。修改后就可以认为 from 和 to 在同一个集合了cc--;// 成功合并，连通块个数减一returntrue;}// 获取连通块个数intgetCC()const{returncc;}};intmaxStability(intn,vector<vector<int>>&edges,intk){UnionFinduf(n);UnionFindallUf(n);intminS1=INT_MAX;// 处理必选边for(constauto&e:edges){intx=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;}// 计算还需选择的边数intleft=uf.getCC()-1;if(left==0){// 只需选必选边returnminS1;}intans=minS1;// 按边权从大到小排序（Kruskal求最大生成树）sort(edges.begin(),edges.end(),[](constvector<int>&a,constvector<int>&b){returna[2]>b[2];// 按稳定性值降序排序});// Kruskal算法选择边for(constauto&e:edges){intx=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;}}}returnans;}intmain(){intn=3;vector<vector<int>>edges={{0,1,4,0},{1,2,3,0},{0,2,1,0}};intk=2;intresult=maxStability(n,edges,k);cout<<result<<endl;// 输出结果return0;}