使用并查集，将水井的打井钱看作是边加入edges中即可
#include<bits/stdc++.h> using namespace std; struct Edge{ int u,v,w; }; vector<int> parent; int find(int x){ if(x!=parent[x]){ parent[x]=find(parent[x]); } return parent[x]; } bool unite(int x,int y){ int findx=find(x); int findy=find(y); if(findx==findy){ return false; } else{ parent[findx]=findy; return true; } } bool cmp(const Edge &a,const Edge &b){ return a.w<b.w; } int main(){ int n; cin>>n; vector<Edge> edges; for(int i=1;i<=n;i++){ int price; cin>>price; edges.push_back({0,i,price}); } vector<vector<int>> k(n+1,vector<int>(n+1)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>k[i][j]; } } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ edges.push_back({i,j,k[i][j]}); } } sort(edges.begin(),edges.end(),cmp); parent.resize(n+1); for(int i=0;i<=n;i++){ parent[i]=i; } int res=0; int ant=0; for(const auto &e:edges){ if(unite(e.u,e.v)){ res+=e.w; ant++; if(ant==n){ break; } } } cout<<res<<endl; return 0; }
