#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
	int u,v,w,next;
}a[10001]={0};
int tot=0;
int last[101]={0};
void add(int x,int y,int z){
	tot++;
	a[tot].u=x;
	a[tot].v=y;
	a[tot].w=z;
	a[tot].next=last[x];
	last[x]=tot;
}
int fa[101]={0};
bool cmp(const node &a,const node &b){
	return a.w<b.w;
}
int find(int x){
	if(!fa[x]) return x;
	else return fa[x]=find(fa[x]);
}
void unio(int x,int y){
	fa[find(x)]=find(y);
}
int main(){
	int q=0;
	int res[1001]={0};
	int x,y;
	int m=0;
	int n;
	while(scanf("%d",&n)!=EOF){
		int i,j,k;
		memset(a,0,sizeof(a));
		memset(fa,0,sizeof(fa));
		tot=0;
		memset(last,0,sizeof(last));
		for(i=1;i<=n;i++)
		 for(j=1;j<=n;j++){
		 	scanf("%d",&x);
		 	if(x&&j<=i){
		 	m++;
		 	add(i,j,x);	
		 }}
		 int ans=0;
		sort(a+1,a+m+1,cmp);
		k=0;
		for(i=1;i<=m;i++){
			if(k==n-1) break;
			if(find(a[i].u)!=find(a[i].v)){
			unio(a[i].u,a[i].v);
			ans+=a[i].w;
			}
		}
	res[q++]=ans;
	}
	for(int i=0;i<q;i++)
	printf("%d\n",res[i]);
	return 0;
}

/*4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0*/

• Re:为何RE！！！！！！！！！！！！！ (702) iamzky 2013-11-07 08:37:24