记录编号	502541	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 挖水井	最终得分	100
用户昵称	6666	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2018-07-27 11:51:42	内存使用	1.36 MiB

//
//  prim.cpp
//  
//
//  Created by apple on 2018/7/27.
//

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
void Min(int &x,int y){if(x>y)x=y;}
const int maxn=305;
int n,N,m,r[maxn];
int F(int x){return r[x]==x?x:r[x]=F(r[x]);}
struct Edge{int x,y,d;}e[maxn*maxn];
bool Cmp(Edge a,Edge b){
    return a.d<b.d;
}
int Kru(){
    sort(e+1,e+m+1,Cmp);
    for(int i=1;i<=N;i++)r[i]=i;
    int cnt=0,res=0;
    for(int i=1;i<=m;i++){
        int rx=F(e[i].x),ry=F(e[i].y);
        if(rx!=ry)r[rx]=ry,cnt++,res+=e[i].d;
        if(cnt==n)return res;
    }
}
int main(){
    freopen("water.in","r",stdin);freopen("water.out","w",stdout);
    scanf("%d",&n);int i,j,x;N=n+1;
    for(i=1;i<=n;i++)
        scanf("%d",&e[++m].d),e[m].x=N,e[m].y=i;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            scanf("%d",&x);
            if(i>j)e[++m].d=x,e[m].x=i,e[m].y=j;
        }
    printf("%d\n",Kru());
}