原题地址：点击打开链接
思路，将自建水库 i 需要的费用转化为边0---->i .
然后用并查集算法求点 0到n的最小生成树即可。
代码：
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct Edge{int u;int v;int cost;}e[90010];int map[310][310],c[310],n,p[310];int comp(Edge e1,Edge e2){return e1.cost<e2.cost;}int find(int x) //找父节点{if(p[x]!=x){p[x]=find(p[x]);}return p[x];}bool bin(int x,int y) //将x，y添加至一个集合{int g,h;g=find(x);h=find(y);if(g==h)return false;p[g]=h;return true;}bool judge() //判断是否所有点都在一个集合{int i,count=0;for(i=0;i<=n;i++){if(p[i]==i)count++;if(count>1)return false;}return true;}int main(){int t,k,i,j,x,res;scanf("%d",&t);while(t--){res=0;k=0;scanf("%d",&n);for(i=0;i<=n;i++)p[i]=i;for(i=1;i<=n;i++){scanf("%d",&x);e[k].u=0;e[k].v=i;e[k++].cost=x;}for(i=1;i<=n;i++)for(j=1;j<=n;j++){scanf("%d",&x);e[k].u=i;e[k].v=j;e[k++].cost=x;}sort(e,e+k,comp);for(i=0;i<k;i++){if(bin(e[i].u,e[i].v)) res+=e[i].cost;if(judge())break;}printf("%d\n",res);}return 0;}
