记录编号	235599	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 挖水井	最终得分	100
用户昵称	Hzoi_Yniverse	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2016-03-11 10:17:29	内存使用	4.14 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000;
int a[maxn][maxn],n,tot,lowcost[maxn],used[maxn];
void Init();
void Prim();
int main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	Init();
	Prim();
	printf("%d\n",tot);
	return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		a[i][n+1]=a[n+1][i]=x;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int x;scanf("%d",&x);
			a[i][j]=a[j][i]=x;
		}
	}
	memset(lowcost,0x7f,sizeof(lowcost));
	memset(used,0,sizeof(used));
}
void Prim(){
	used[1]=1;
	for(int i=1;i<=n+1;i++){
		lowcost[i]=a[i][1];
	}
	for(int i=1;i<=n;i++){
		int min=0x7f7f7f7f,k;
		for(int j=1;j<=n+1;j++){
			if(!used[j]&&lowcost[j]<min){
				min=lowcost[j];
				k=j;
			}
		}
		used[k]=1;
		tot+=lowcost[k];
		for(int j=1;j<=n+1;j++){
			if(!used[j]&&a[j][k]<lowcost[j]){
				lowcost[j]=a[j][k];
			}
		}
	}
}