要使n个农场从其他农场引水，或自己打井。

对于每个农场，最小花费为与min（自己打井，min（与其他农场连接））；

当然，至少有一个农场打井。

这样选择后，得到了若干个联通块，每个块中有一个农场打井。

那么可以看出，每个农场需要直接或间接与水源相连。

把水源看作一个中转节点（虚根），每个农场与水源连边，边权即为修建水库的花费。

再将每对农场之间连边，所求即为这个图上的一个最小生成树。

这也符合至少有一个节点连接水源的要求。

 

代码不难，但是建立虚根的思路很重要。

代码如下

 

#include
      
       #include
       
        #include
        
         #include
         
          #define MogeKo qwq#include
          
           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;}