题目

我们建立一个超级源点，每个点都与超级源点相连，他们的权值为在该点建立发电站的费用，剩下的将其余点相连，权值为连接到已经通电的发电站费用，我们跑一遍最小生成树即可将他们全部相连，并且费用最小。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define x first
#define y second
typedef pair<int,int> PII;
const int N=1e5+10;
int n,m,k,ans,ecnt;int fa[N],head[N];struct edge {int u,v,w,next;
} E[N<<1];bool cmp(edge a,edge b) {return a.w<b.w;
}
void add(int u,int v,int w) {E[++ecnt].u=u;E[ecnt].v=v;E[ecnt].w=w;E[ecnt].next=head[u];head[u]=ecnt;
}int findFa(int x) {return x==fa[x]?x:fa[x]=findFa(fa[x]);
}int kruskal() {sort(E+1,E+1+ecnt,cmp);int cnt=0,sum=0;for(int i=1; i<=ecnt; i++) {int x=E[i].u;int y=E[i].v;int fx=findFa(x),fy=findFa(y);if(fx!=fy) {fa[fx]=fy; cnt++;sum+=E[i].w;}if(cnt==n)break;}return sum;
}int main() {cin>>n;int v;for(int i=1;i<=n;i++)fa[i]=i; //0号点为超级源点for(int i=1; i<=n; i++) {cin>>v;add(0,i,v);add(i,0,v);}for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {cin>>v;if(v) {add(i,j,v);add(j,i,v);}}}cout<<kruskal();return 0;
}