记录编号	382097	评测结果	AWAWWAWAWA
题目名称	[USACO Oct08] 挖水井	最终得分	50
用户昵称	TARDIS	是否通过	未通过
代码语言	C++	运行时间	0.017 s
提交时间	2017-03-12 22:00:24	内存使用	0.61 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define maxn 90001
#define itn int
using namespace std;
struct edge{
	int from;
	int to;
	int dist;
	bool operator < (const edge&rhs)const{
		return dist<rhs.dist;
	}
};
int n;int w[maxn];edge E[maxn];int Mmin=2000000;
int f[maxn];int temp,cnt=0,ans=0;
inline int ff(int x){
	if (f[x]==x) return x;
	return f[x]=ff(f[x]);
}
inline bool unionn(int x,int y){
	int fax=ff(x);
	int fay=ff(y);
	if (fax==fay) return true;
	else {
		f[fax]=fay;
		return false;
	}
}
inline void kr(){
	for (int i=1;i<=cnt;i++){
		if (unionn(E[i].from,E[i].to)) continue;
		else {
			ans+=E[i].dist;
		}
	}
}
inline void readln(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&w[i]);
		Mmin=min(Mmin,w[i]);
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			scanf("%d",&temp);
			E[cnt].from=i;E[cnt].to=j;E[cnt].dist=temp;
			cnt++;	
		}
	}
	for (int i=1;i<=n;i++){
		f[i]=i;
	}
	sort(E+1,E+cnt+1);
}
inline void p(){
	ans+=Mmin;
	printf("%d",ans);
	fclose(stdin);fclose(stdout);
}
int Main(){
	readln();
	kr();
	p();
	return 0;
}
int main(){;}
int xlm=Main();