题解
如果没说全部连通的话就会形成一个特殊的局面：
森林。
把一个无向森林结合起来的常用方法就是加点。
加一个超级源，使打井变成这个源到节点的边权，再MST即可。
数据小，貌似暴力也行？1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using namespace std;
int mat[405][405],w[405],n;
int vis[405],mini[405];
int prim(int S){
memset(mini,0x3f,sizeof(mini));
mini[S]=0;
int i,j,_min,at,ans=0;
for(i=0;i<n;i++){
for(at=-1,j=0;j<n;j++)
if(!vis[j]&&(at<0||mini[j]<mini[at]))
at=j;
vis[at]=1,ans+=mini[at];
for(j=0;j<n;j++)
mini[j]=min(mini[j],mat[at][j]);
}
return ans;
}
int main(){
scanf("%d",&n);
int i,j;
for(i=0;i<n;i++)
scanf("%d",&w[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&mat[i][j]);
for(int i=0;i<n;i++)
mat[i][n]=mat[n][i]=w[i];
mat[n][n]=0;
n++;
printf("%d\n",prim(n-1));
return 0;
}