一.题目
P1550 [USACO08OCT] Watering Hole G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二.分析
1.我们是要使所有的农场都要有水
2.可以从起点引水，也可以互相引水。
3.费用要最小
这时我们可以想到最小生成树，建立一个虚拟节点即可。思路一目了然。
三.参考代码
#include<bits/stdc++.h>
#define maxn 91000
using namespace std;
struct Edge{
int u,v,w;
}edge[maxn];
int n,cnt;
int fa[305];
int find(int x){
return x==fa[x] ? x :fa[x]=find(fa[x]);
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
fa[fx]=fy;
}
bool cmp(Edge a,Edge b){
return a.w<b.w;
}
long long ans;
void kruskal(){
sort(edge+1,edge+cnt+1,cmp);
int tot=0;
for(int i=1;i<=cnt;i++){
int x=edge[i].u,y=edge[i].v;
if(find(x)==find(y)) continue;
tot++;
ans+=edge[i].w;
merge(x,y);
if(tot==n) return;
}
}
int main(){
scanf("%d",&n);
int w;
for(int i=1;i<=n;i++){
scanf("%d",&w);
edge[++cnt]=(Edge){0,i,w};
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&w);
if(w!=0){
edge[++cnt]=(Edge){i,j,w};
}
}
}
for(int i=1;i<=n;i++) fa[i]=i;
kruskal();
cout<<ans;
return 0;
}
四.总结
当看到这些条件，可以想到最小生成树
1.涉及到每个节点
2.最小/最大的值文章来源：https://www.toymoban.com/news/detail-685602.html
3.一般都要用到虚拟节点，以处理初始点文章来源地址https://www.toymoban.com/news/detail-685602.html
到了这里，关于【图论】最小生成树的应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![【算法每日一练]-图论（保姆级教程篇7 最小生成树 ，并查集模板篇）#村村通 #最小生成树](https://imgs.yssmx.com/Uploads/2024/02/759236-1.png)
