2023-08-04：村里面一共有 n 栋房子

我们希望通过建造水井和铺设管道来为所有房子供水。

对于每个房子 i，我们有两种可选的供水方案：

一种是直接在房子内建造水井

成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）

另一种是从另一口井铺设管道引水

数组 pipes 给出了在房子间铺设管道的成本

其中每个 pipes[j] = [house1j, house2j, costj]

代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。

请返回 为所有房子都供水的最低总成本 。

这道题很高频，引起注意，

本身也不难，转化一下变成最小生成树的问题即可。

输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]。

输出：3。

来自小红书、字节跳动。

答案2023-08-04：

大体过程如下：

1.初始化：

1.1.创建边数组 edges 用于存储管道的信息。

1.2.将每个房子 i 作为一个独立的连通分量，创建并查集的父数组 father[i] 初始化为 i。

1.3.创建每个房子的大小数组 size[i] 初始化为 1。

1.4.创建辅助数组 help 用于路径压缩。

2.构建边数组：

2.1.将每个房子 i 内建造水井的成本 wells[i-1] 加入边数组 edges。

2.2.将每个管道 [house1j, house2j, costj] 的信息加入边数组 edges。

3.对边数组进行排序：

3.1.根据边的成本从小到大对边数组 edges 进行排序。

4.构建并查集：

4.1.调用 build(n) 函数来初始化并查集。

5.最小生成树的构建与计算最低总成本： 5.1.初始化 ans = 0，用于记录最低总成本。

5.2.遍历边数组 edges，对于每条边 edges[i]，执行以下步骤：

5.2.1.判断边 edges[i] 的两个节点是否连通（使用并查集中的 find() 函数）：

5.2.1.1.若不连通，则将这两个节点合并（使用并查集中的 union() 函数）。

5.2.1.2.同时累加上该边的成本 edges[i][2] 到总成本 ans 中。

6.返回最低总成本 ans。

总的时间复杂度：O((n+m)log(n+m))，其中 n 是房子数量，m 是管道数量，因为对边数组进行了排序。

总的空间复杂度：O(n+m)，其中 n 是房子数量，m 是管道数量（边的数量）。

go完整代码如下：

packagemainimport("fmt""sort")constMAXN=10010varedges[][3]intvaresizeintvarfather[MAXN]intvarsize[MAXN]intvarhelp[MAXN]intfuncbuild(nint){fori:=0;i<=n;i++{father[i]=isize[i]=1}}funcfind(iint)int{s:=0fori!=father[i]{help[s]=ii=father[i]s++}fors>0{s--father[help[s]]=i}returni}funcunion(i,jint)bool{f1:=find(i)f2:=find(j)iff1!=f2{ifsize[f1]>=size[f2]{father[f2]=f1size[f1]+=size[f2]}else{father[f1]=f2size[f2]+=size[f1]}returntrue}returnfalse}funcminCostToSupplyWater(nint,wells[]int,pipes[][]int)int{esize=0fori:=0;iedges=append(edges,[3]int{0,i+1,wells[i]})esize++}fori:=0;iedges=append(edges,[3]int{pipes[i][0],pipes[i][1],pipes[i][2]})esize++}sort.Slice(edges,func(i,jint)bool{returnedges[i][2]})build(n)ans:=0fori:=0;iifunion(edges[i][0],edges[i][1]){ans+=edges[i][2]}}returnans}funcmain(){n:=3wells:=[]int{1,2,2}pipes:=[][]int{{1,2,1},{2,3,1}}result:=minCostToSupplyWater(n,wells,pipes)fmt.Println(result)}

rust代码如下：

constMAXN:i32=10010;staticmutEDGES:[[i32;3];(MAXN<<1)asusize]=[[0;3];(MAXN<<1)asusize];staticmutESIZE:i32=0;staticmutFATHER:[i32;MAXNasusize]=[0;MAXNasusize];staticmutSIZE:[i32;MAXNasusize]=[0;MAXNasusize];staticmutHELP:[i32;MAXNasusize]=[0;MAXNasusize];fnbuild(n:i32){foriin0..=n{unsafe{FATHER[iasusize]=i;SIZE[iasusize]=1;}}}fnfind(i:i32)->i32{letmuts=0;unsafe{letmutindex=i;whileindex!=FATHER[indexasusize]{HELP[s]=index;index=FATHER[indexasusize];s+=1;}whiles>0{s-=1;FATHER[HELP[s]asusize]=index;}returnindex;}}fnunion(i:i32,j:i32)->bool{letf1=find(i);letf2=find(j);unsafe{iff1!=f2{ifSIZE[f1asusize]>=SIZE[f2asusize]{FATHER[f2asusize]=f1;SIZE[f1asusize]+=SIZE[f2asusize];}else{FATHER[f1asusize]=f2;SIZE[f2asusize]+=SIZE[f1asusize];}returntrue;}else{returnfalse;}}}fnmin_cost_to_supply_water(n:i32,wells:&[i32],pipes:&[[i32;3]])->i32{unsafe{ESIZE=0;foriin0..n{EDGES[ESIZEasusize][0]=0;EDGES[ESIZEasusize][1]=i+1;EDGES[ESIZEasusize][2]=wells[iasusize];ESIZE+=1;}foriin0..pipes.len(){EDGES[ESIZEasusize][0]=pipes[i][0]asi32;EDGES[ESIZEasusize][1]=pipes[i][1]asi32;EDGES[ESIZEasusize][2]=pipes[i][2];ESIZE+=1;}EDGES[0..ESIZEasusize].sort_by(|a,b|a[2].cmp(&b[2]));build(n);letmutans=0;foriin0..ESIZE{ifunion(EDGES[iasusize][0],EDGES[iasusize][1]){ans+=EDGES[iasusize][2];}}returnans;}}fnmain(){letn=3;letwells=[1,2,2];letpipes=[[1,2,1],[2,3,1]];letresult=min_cost_to_supply_water(n,&wells,&pipes);println!("Minimumcosttosupplywater:{}",result);}

c++完整代码如下：

#include#include#include#includeusingnamespacestd;constintMAXN=10010;vector>edges;intfather[MAXN];intsize2[MAXN];inthelp[MAXN];voidbuild(intn){for(inti=0;i<=n;i++){father[i]=i;size2[i]=1;}}intfind(inti){ints=0;while(i!=father[i]){help[s++]=i;i=father[i];}while(s>0){father[help[--s]]=i;}returni;}boolunionSet(inti,intj){intf1=find(i);intf2=find(j);if(f1!=f2){if(size2[f1]>=size2[f2]){father[f2]=f1;size2[f1]+=size2[f2];}else{father[f1]=f2;size2[f2]+=size2[f1];}returntrue;}else{returnfalse;}}intminCostToSupplyWater(intn,vector&wells,vector>&pipes){edges.clear();for(inti=0;iedges.push_back({0,i+1,wells[i]});}for(inti=0;iedges.push_back({pipes[i][0],pipes[i][1],pipes[i][2]});}sort(edges.begin(),edges.end(),[](constarray&a,constarray&b){returna[2]});build(n);intans=0;for(inti=0;iif(unionSet(edges[i][0],edges[i][1])){ans+=edges[i][2];}}returnans;}intmain(){intn=3;vectorwells={1,2,2};vector>pipes={{1,2,1},{2,3,1}};intresult=minCostToSupplyWater(n,wells,pipes);cout<<"Minimumcosttosupplywater:"<return0;}

c完整代码如下：

#include#include#defineMAXN10010intedges[MAXN<<1][3];intesize;intfather[MAXN];intsize[MAXN];inthelp[MAXN];voidbuild(intn){for(inti=0;i<=n;i++){father[i]=i;size[i]=1;}}intfind(inti){ints=0;while(i!=father[i]){help[s++]=i;i=father[i];}while(s>0){father[help[--s]]=i;}returni;}intunion2(inti,intj){intf1=find(i);intf2=find(j);if(f1!=f2){if(size[f1]>=size[f2]){father[f2]=f1;size[f1]+=size[f2];}else{father[f1]=f2;size[f2]+=size[f1];}return1;}else{return0;}}intminCostToSupplyWater(intn,intwells[],intpipes[][3],intpipesSize){esize=0;for(inti=0;iedges[esize][0]=0;edges[esize][1]=i+1;edges[esize][2]=wells[i];}for(inti=0;iedges[esize][0]=pipes[i][0];edges[esize][1]=pipes[i][1];edges[esize][2]=pipes[i][2];}//Sortedgesbasedonthethirdcolumn(weights)for(inti=0;ifor(intj=0;jif(edges[j][2]>edges[j+1][2]){inttemp[3];temp[0]=edges[j][0];temp[1]=edges[j][1];temp[2]=edges[j][2];edges[j][0]=edges[j+1][0];edges[j][1]=edges[j+1][1];edges[j][2]=edges[j+1][2];edges[j+1][0]=temp[0];edges[j+1][1]=temp[1];edges[j+1][2]=temp[2];}}}build(n);intans=0;for(inti=0;iif(union2(edges[i][0],edges[i][1])){ans+=edges[i][2];}}returnans;}intmain(){intn=3;intwells[]={1,2,2};intpipes[][3]={{1,2,1},{2,3,1}};intpipesSize=sizeof(pipes)/sizeof(pipes[0]);intresult=minCostToSupplyWater(n,wells,pipes,pipesSize);printf("Minimumcosttosupplywater:%d\n",result);return0;}