题目描述某城市要建 5G 网络已经选了 N 个地点放基站编号 1 到 N。现在要在基站之间拉光纤让所有人都能互相连通。有些基站对之间已经铺好了光纤有些还没有。每条候选光纤有个建设成本。求让全部基站互联互通的最小新增成本。如果无论如何都连不通输出 -1。N不超过 20候选光纤数量M不超过N * (N - 1) / 2。讲个故事老张的光纤工程队老张是包工头接了个 5G 基站拉光纤的活儿。到现场一看有些基站之间已经有光纤了这部分不用花钱。剩下的得他自己铺每条报价不一样。老张心想先把不要钱的连上再把便宜的连上只要所有基站都在同一个网里活儿就算干完了。这不就是最小生成树吗核心原理最小生成树 并查集已经铺好的光纤相当于成本为 0 的边。问题变成在一个无向图中选一些边把 N 个点连起来总成本最小。这就是最小生成树MST。因为 N 很小用 Kruskal 算法足够把所有边按成本排序已经铺好的边成本视为 0排在最前面用并查集一条条加边不形成环就加入如果末尾所有点都在一个集合输出总成本否则输出 -1怎么实现读入 N 和 M读入每条边X Y Z P其中 P 0 表示未建P 1 表示已建已建边的成本改成 0然后按成本排序并查集初始化逐条加边统计连通块数量判断是否能建网代码实现C 语言#includestdio.h#includestdlib.htypedefstruct{intu,v,cost;}Edge;intcmp(constvoid*a,constvoid*b){return((Edge*)a)-cost-((Edge*)b)-cost;}intparent[25];intfind(intx){returnparent[x]x?x:(parent[x]find(parent[x]));}intsolve(intn,Edge edges[],intm){qsort(edges,m,sizeof(Edge),cmp);for(inti1;in;i)parent[i]i;inttotal0,edgesUsed0;for(inti0;im;i){intuedges[i].u,vedges[i].v;intpufind(u),pvfind(v);if(pu!pv){parent[pu]pv;totaledges[i].cost;edgesUsed;}}if(edgesUsed!n-1)return-1;returntotal;}C#includebits/stdc.husingnamespacestd;structEdge{intu,v,cost;booloperator(constEdgeo)const{returncosto.cost;}};structUnionFind{vectorintp;UnionFind(intn){p.resize(n1);iota(p.begin(),p.end(),0);}intfind(intx){returnp[x]x?x:p[x]find(p[x]);}boolunite(intx,inty){xfind(x);yfind(y);if(xy)returnfalse;p[x]y;returntrue;}};intsolve(intn,vectorEdgeedges){sort(edges.begin(),edges.end());UnionFinduf(n);inttotal0,used0;for(autoe:edges){if(uf.unite(e.u,e.v)){totale.cost;used;}}returnusedn-1?total:-1;}Javaimportjava.util.*;publicclassMain{staticclassEdgeimplementsComparableEdge{intu,v,cost;Edge(intu,intv,intcost){this.uu;this.vv;this.costcost;}publicintcompareTo(Edgeo){returnthis.cost-o.cost;}}staticclassUnionFind{int[]p;UnionFind(intn){pnewint[n1];for(inti0;in;i)p[i]i;}intfind(intx){returnp[x]x?x:(p[x]find(p[x]));}booleanunite(intx,inty){xfind(x);yfind(y);if(xy)returnfalse;p[x]y;returntrue;}}publicstaticintsolve(intn,Edge[]edges){Arrays.sort(edges);UnionFindufnewUnionFind(n);inttotal0,used0;for(Edgee:edges){if(uf.unite(e.u,e.v)){totale.cost;used;}}returnusedn-1?total:-1;}}JavaScriptclassUnionFind{constructor(n){this.pArray.from({length:n1},(_,i)i);}find(x){returnthis.p[x]x?x:(this.p[x]this.find(this.p[x]));}unite(x,y){xthis.find(x);ythis.find(y);if(xy)returnfalse;this.p[x]y;returntrue;}}functionsolve(n,edges){edges.sort((a,b)a.cost-b.cost);constufnewUnionFind(n);lettotal0,used0;for(const{u,v,cost}ofedges){if(uf.unite(u,v)){totalcost;used;}}returnusedn-1?total:-1;}PythonclassUnionFind:def__init__(self,n):self.plist(range(n1))deffind(self,x):ifself.p[x]!x:self.p[x]self.find(self.p[x])returnself.p[x]defunite(self,x,y):x,yself.find(x),self.find(y)ifxy:returnFalseself.p[x]yreturnTruedefsolve(n,edges):edges.sort(keylambdae:e[2])ufUnionFind(n)totalused0foru,v,costinedges:ifuf.unite(u,v):totalcost used1returntotalifusedn-1else-1复杂度分析排序O(M * log M)并查集操作O(M * α(N))α 是阿克曼函数反函数约等于常数总时间复杂度O(M * log M)空间复杂度O(N M)总结一下5G 网络建设 最小生成树的变体。唯一的小 trick 是已经铺好的光纤看成成本为 0 的边这样 Kruskal 一视同仁自然先选免费的再选便宜的。末尾判断一下用了多少条边。N 个点要连成一个树必须刚好用 N - 1 条边。少了就说明不连通。你平时写并查集是习惯路径压缩还是按秩合并欢迎在评论区聊聊。