题目描述

某城市要建 5G 网络，已经选了 N 个地点放基站，编号 1 到 N。现在要在基站之间拉光纤，让所有人都能互相连通。

有些基站对之间已经铺好了光纤，有些还没有。每条候选光纤有个建设成本。求让全部基站互联互通的最小新增成本。如果无论如何都连不通，输出 -1。

N不超过 20，候选光纤数量M不超过N * (N - 1) / 2。

讲个故事：老张的光纤工程队

老张是包工头，接了个 5G 基站拉光纤的活儿。

到现场一看，有些基站之间已经有光纤了，这部分不用花钱。剩下的得他自己铺，每条报价不一样。

老张心想：先把不要钱的连上，再把便宜的连上，只要所有基站都在同一个"网"里，活儿就算干完了。

这不就是最小生成树吗？

核心原理：最小生成树 + 并查集

已经铺好的光纤，相当于成本为 0 的边。问题变成：

在一个无向图中，选一些边把 N 个点连起来，总成本最小。

这就是最小生成树（MST）。

因为 N 很小，用 Kruskal 算法足够：

1. 把所有边按成本排序
2. 已经铺好的边成本视为 0，排在最前面
3. 用并查集一条条加边，不形成环就加入
4. 如果末尾所有点都在一个集合，输出总成本；否则输出 -1

怎么实现？

1. 读入 N 和 M
2. 读入每条边：X Y Z P，其中 P = 0 表示未建，P = 1 表示已建
3. 已建边的成本改成 0，然后按成本排序
4. 并查集初始化，逐条加边
5. 统计连通块数量，判断是否能建网

代码实现

C 语言

#include<stdio.h>#include<stdlib.h>typedefstruct{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(inti=1;i<=n;i++)parent[i]=i;inttotal=0,edgesUsed=0;for(inti=0;i<m;i++){intu=edges[i].u,v=edges[i].v;intpu=find(u),pv=find(v);if(pu!=pv){parent[pu]=pv;total+=edges[i].cost;edgesUsed++;}}if(edgesUsed!=n-1)return-1;returntotal;}

C++

#include<bits/stdc++.h>usingnamespacestd;structEdge{intu,v,cost;booloperator<(constEdge&o)const{returncost<o.cost;}};structUnionFind{vector<int>p;UnionFind(intn){p.resize(n+1);iota(p.begin(),p.end(),0);}intfind(intx){returnp[x]==x?x:p[x]=find(p[x]);}boolunite(intx,inty){x=find(x);y=find(y);if(x==y)returnfalse;p[x]=y;returntrue;}};intsolve(intn,vector<Edge>edges){sort(edges.begin(),edges.end());UnionFinduf(n);inttotal=0,used=0;for(auto&e:edges){if(uf.unite(e.u,e.v)){total+=e.cost;used++;}}returnused==n-1?total:-1;}

Java

importjava.util.*;publicclassMain{staticclassEdgeimplementsComparable<Edge>{intu,v,cost;Edge(intu,intv,intcost){this.u=u;this.v=v;this.cost=cost;}publicintcompareTo(Edgeo){returnthis.cost-o.cost;}}staticclassUnionFind{int[]p;UnionFind(intn){p=newint[n+1];for(inti=0;i<=n;i++)p[i]=i;}intfind(intx){returnp[x]==x?x:(p[x]=find(p[x]));}booleanunite(intx,inty){x=find(x);y=find(y);if(x==y)returnfalse;p[x]=y;returntrue;}}publicstaticintsolve(intn,Edge[]edges){Arrays.sort(edges);UnionFinduf=newUnionFind(n);inttotal=0,used=0;for(Edgee:edges){if(uf.unite(e.u,e.v)){total+=e.cost;used++;}}returnused==n-1?total:-1;}}

JavaScript

classUnionFind{constructor(n){this.p=Array.from({length:n+1},(_,i)=>i);}find(x){returnthis.p[x]===x?x:(this.p[x]=this.find(this.p[x]));}unite(x,y){x=this.find(x);y=this.find(y);if(x===y)returnfalse;this.p[x]=y;returntrue;}}functionsolve(n,edges){edges.sort((a,b)=>a.cost-b.cost);constuf=newUnionFind(n);lettotal=0,used=0;for(const{u,v,cost}ofedges){if(uf.unite(u,v)){total+=cost;used++;}}returnused===n-1?total:-1;}

Python

classUnionFind:def__init__(self,n):self.p=list(range(n+1))deffind(self,x):ifself.p[x]!=x:self.p[x]=self.find(self.p[x])returnself.p[x]defunite(self,x,y):x,y=self.find(x),self.find(y)ifx==y:returnFalseself.p[x]=yreturnTruedefsolve(n,edges):edges.sort(key=lambdae:e[2])uf=UnionFind(n)total=used=0foru,v,costinedges:ifuf.unite(u,v):total+=cost used+=1returntotalifused==n-1else-1

复杂度分析

• 排序：O(M * log M)
• 并查集操作：O(M * α(N))，α 是阿克曼函数反函数，约等于常数
• 总时间复杂度：O(M * log M)
• 空间复杂度：O(N + M)

总结一下

5G 网络建设 = 最小生成树的变体。

唯一的小 trick 是：已经铺好的光纤看成成本为 0 的边，这样 Kruskal 一视同仁，自然先选免费的，再选便宜的。

末尾判断一下用了多少条边。N 个点要连成一个树，必须刚好用 N - 1 条边。少了就说明不连通。

你平时写并查集是习惯路径压缩还是按秩合并？欢迎在评论区聊聊。