今天上课时叕听了一遍最小生成树，最小生成树的知识就不必多说了吧，对于这道题，我们将打通的费用可以看作边权，而打井呢又可以看作把它与0点连接，也就是我们再新建一个点
然后就是kruskal求最小生成树了
#include<bits/stdc++.h> using namespace std; const int N=550; const int maxn=1e6+7; struct node{ int x; int y; int v; }tree[maxn*3]; int n; int p[N][N]; int a[maxn]; int fa[maxn]; int cnt,ans,num; int get(int x){ if(x!=fa[x]) return fa[x]=get(fa[x]); } void united(int x,int y){ fa[x]=y; } bool cmp(node a,node b){ return a.v<b.v; } void kruskal(){ sort(tree+1,tree+1+cnt,cmp); ans=0,num=0; for(int i=1;i<=cnt;i++){ int f1=get(tree[i].x); int f2=get(tree[i].y); if(f1!=f2){ united(f1,f2); ans+=tree[i].v; num++; } if(num>n){ break; } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); tree[++cnt].x=0; tree[cnt].y=i; tree[cnt].v=a[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&p[i][j]); tree[++cnt].x=i; tree[cnt].y=j; tree[cnt].v=p[i][j]; } } for(int i=1;i<=cnt;i++){ fa[i]=i; } kruskal(); printf("%d",ans); return 0; }