题目链接：

https://www.luogu.org/problemnew/show/P1550

思路：

1：把地当做0节点，那么打井的费用，就是各节点到0节点的费用

2：跑kruskal

算法：

1：kruskal

#include <bits/stdc++.h>using namespace std;
const int maxn=301;
int n,parent[maxn],rank[maxn],c;struct edge
{int f,t;long long quan;
}e[maxn*maxn];bool cmp(edge a,edge b)
{return a.quan<b.quan;
}void init()
{for(int i=0;i<=n;i++){parent[i]=-1;rank[i]=0;}
}int find_root(int x)
{int x_root=x;while(parent[x_root]!=-1){x_root=parent[x_root];}return x_root;
}int unionxy(int x,int y)
{int x_root=find_root(x);int y_root=find_root(y);if(x_root==y_root)return 0;else{if(rank[x_root]>rank[y_root])parent[y_root]=x_root;else if(rank[x_root]<rank[y_root])parent[x_root]=y_root;else{parent[x_root]=y_root;rank[y_root]++;}return 1;}
}int main()
{cin>>n;init();for(int i=0;i<n;i++){cin>>c;e[i].f=0;e[i].t=i+1;e[i].quan=c;}int j=n;for(int i=1;i<=n;i++){for(int t=1;t<=n;t++){cin>>c;e[j].f=i;e[j].t=t;e[j].quan=c;j++;}}sort(e,e+n*(n+1),cmp);int k=0;long long sum=0;for(int i=0;i<n*(n+1);i++){if(k==n)break;if(unionxy(e[i].f,e[i].t)){k++;sum+=e[i].quan;}}if(k==n)cout<<sum<<endl;return 0;
}