深圳网站建设及推广小程序云开发费用

深圳网站建设及推广,小程序云开发费用,郑州专业网站制作费用报价,哪里网站备案2025-12-12#xff1a;升级后最大生成树稳定性。用go语言#xff0c;给出一个包含编号 0 到 n-1 的 n 个节点的无向图#xff0c;边的列表 edges 中每条记录为 [ui, vi, si, musti]#xff0c;含义如下#xff1a;ui、vi#xff1a;该条边连接的两个端点#xff08;无向…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 次总升级、且所有 musti1 的边必须被选入且不能升级的前提下找出任意一棵合法生成树可以达到的最大稳定性若不存在任何能把所有节点连通的合法生成树则返回 -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(fmtmathslices)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)ifxy{// 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]ifmust0{if!uf.merge(x,y){// 必选边成环return-1}minS1min(minS1,s)}allUf.merge(x,y)}ifallUf.cc1{// 图不连通return-1}left:uf.cc-1ifleft0{// 只需选必选边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]ifmust0uf.merge(x,y){ifleftk{ansmin(ans,s)}else{ansmin(ans,s*2)}left--ifleft0{// 已经得到生成树了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.falist(range(n))# 代表元self.ccn# 连通块个数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,yself.find(from_),self.find(to)ifxy:returnFalseself.fa[x]y self.cc-1returnTruedefmax_stability(n:int,edges:list[list[int]],k:int)-int:ufUnionFind(n)all_ufUnionFind(n)min_s1math.inf# 处理必选边foreinedges:x,y,s,musteifmust0:ifnotuf.merge(x,y):# 必选边成环return-1min_s1min(min_s1,s)all_uf.merge(x,y)# 检查图的连通性ifall_uf.cc1:return-1leftuf.cc-1# 还需连接的连通块数ifleft0:# 只需选必选边returnmin_s1 ansmin_s1# Kruskal 算法求最大生成树按稳定度降序排序edges.sort(keylambdae:-e[2])foreinedges:x,y,s,musteifmust0anduf.merge(x,y):ifleftk:ansmin(ans,s)else:ansmin(ans,s*2)left-1ifleft0:# 已经得到生成树breakreturnansif__name____main__:n3edges[[0,1,4,0],[1,2,3,0],[0,2,1,0]]k2resultmax_stability(n,edges,k)print(result)# 输出: 6C完整代码如下#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;classUnionFind{private:vectorintfa;// 代表元intcc;// 连通块个数public:// 构造函数初始化n个独立集合UnionFind(intn):cc(n){fa.resize(n);// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己for(inti0;in;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){intxfind(from);intyfind(to);if(xy){// from 和 to 在同一个集合不做合并returnfalse;}fa[x]y;// 合并集合。修改后就可以认为 from 和 to 在同一个集合了cc--;// 成功合并连通块个数减一returntrue;}// 获取连通块个数intgetCC()const{returncc;}};intmaxStability(intn,vectorvectorintedges,intk){UnionFinduf(n);UnionFindallUf(n);intminS1INT_MAX;// 处理必选边for(constautoe:edges){intxe[0],ye[1],se[2],muste[3];if(must0){if(!uf.merge(x,y)){// 必选边成环return-1;}minS1min(minS1,s);}allUf.merge(x,y);}// 检查图的连通性if(allUf.getCC()1){// 图不连通return-1;}// 计算还需选择的边数intleftuf.getCC()-1;if(left0){// 只需选必选边returnminS1;}intansminS1;// 按边权从大到小排序Kruskal求最大生成树sort(edges.begin(),edges.end(),[](constvectorinta,constvectorintb){returna[2]b[2];// 按稳定性值降序排序});// Kruskal算法选择边for(constautoe:edges){intxe[0],ye[1],se[2],muste[3];if(must0uf.merge(x,y)){if(leftk){ansmin(ans,s);}else{ansmin(ans,s*2);}left--;if(left0){// 已经得到生成树了break;}}}returnans;}intmain(){intn3;vectorvectorintedges{{0,1,4,0},{1,2,3,0},{0,2,1,0}};intk2;intresultmaxStability(n,edges,k);coutresultendl;// 输出结果return0;}