记录编号	418681	评测结果	ATWAWWAWTT
题目名称	新的开始	最终得分	30
用户昵称	liuyu	是否通过	未通过
代码语言	C++	运行时间	3.060 s
提交时间	2017-07-01 08:37:48	内存使用	2.42 MiB

#include<cstdio>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int n,p[500][500],s,maaa=1e9;
int f[500],vis[500];
vector<int>vec[500];
struct edg{
	int fr,to,w;
}e[100000];
int cnt=1,sum=0;

bool cmp(edg a,edg b){return a.w<=b.w;}
int find(int x){return f[x]==x ? x:find(f[x]);}
void kruskar(){
    for(int i=1;i<=n;i++)f[i]=i;//cout<<"A";
    sort(e+1,e+cnt,cmp);
    for(int i=1;i<cnt;i++){
	int a=find(e[i].fr);
	int b=find(e[i].to);
	if(a!=b){
	    f[a]=b;
	    sum+=e[i].w;
	}
    }
}
void init()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s);
		maaa=min(maaa,s);
	}
	sum=maaa;
	for(int i=1;i<=n;i++)
		 for(int j=1;j<=n;j++)
		 {
			 scanf("%d",&p[i][j]);
			 if(p[i][j]!=0){
			     e[cnt].fr=i;
			     e[cnt].to=j;
			     e[cnt].w=p[i][j];
			     cnt++;
			 }
	     }
}
int main()
{
	freopen("newstart.in","r",stdin);
	freopen("newstart.out","w",stdout);
	init();
	kruskar();
	cout<<sum;

	return 0;
}