要使n个农场从其他农场引水，或打井。
对于每个农场，最小花费为与min（自己打井，min（与其他农场连接））；
当然，至少有一个农场打井。
这样选择后，得到了若干个联通块，每个块中有一个农场打井。
那么可以看出，每个农场需要直接或间接与水源相连。
把水源看作一个中转节点（虚根），每个农场与水源连边，边权即为修建水库的花费。
再将每对农场之间连边，所求即为这个图上的一个最小生成树。
这也符合至少有一个节点连接水源的要求。
代码不难，但是建立虚根的思路很重要。
代码如下
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define MogeKo qwq #include<algorithm> using namespace std; const int maxn = 1e6; int n,x,cnt,ans,fa[maxn]; struct node { int from,to,val; bool operator < (const node & N) const { return val < N.val; } } e[maxn]; void add(int a,int b,int c) { e[++cnt].from = a; e[cnt].to = b; e[cnt].val = c; } int getfa(int x) { if(fa[x] == x)return x; else return fa[x] = getfa(fa[x]); } void kruskal(){ for(int i = 1;i <= cnt;i++){ int x = getfa(e[i].from); int y = getfa(e[i].to); if(x == y)continue; fa[x] = y; ans += e[i].val; } } int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++) fa[i] = i; for(int i = 1;i <= n;i++){ scanf("%d",&x); add(0,i,x); } for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++){ scanf("%d",&x); if(j <= i)continue; add(i,j,x); } sort(e+1,e+cnt+1); kruskal(); printf("%d",ans); return 0; }
Luogu P1550 [USACO08OCT]打井Watering Hole
原文：https://www.cnblogs.com/mogeko/p/10914111.html
