【图论】最小生成树的应用

一.题目

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.最小/最大的值

3.一般都要用到虚拟节点，以处理初始点