#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 150
#define M 21000
int n;
struct arr{
	int ff,tt,ww;
}c[M];
int r[M];
int f[N];
int tot = 0;
inline void add(int x,int y,int z){
	c[++tot].ff = x;
	c[tot].tt = y;
	c[tot].ww = z;
	return;
}

bool comp(const int a,const int b){
	return c[a].ww < c[b].ww;
}

int find(int x){
	return f[x] == x ? x:f[x] = find(f[x]);
}

int kruscal(){
	int ans = 0;
	for (int i = 1; i<=n; i++) f[i] = i;
	for (int i = 1; i<=tot; i++) r[i] = i;
	sort(r + 1,r + 1 + tot,comp);
	for (int i = 1; i<=tot; i++){
		int y = r[i];
		int fx = find(c[y].ff);
		int fy = find(c[y].tt);
		if (fx != fy){
			ans += c[y].ww;
			f[fx] = fy;
		}
	}
	return ans;
}

int main(){
	while (scanf("%d",&n) != EOF){
		int w;
		memset(c,0,sizeof(c));
		for (int i = 1; i<=n; i++){
			for (int j = 1; j<=n; j++){
				scanf("%d",&w);
				if (i < j) add(i,j,w);
			}
		}
		printf("%d\n",kruscal());
	}
	return 0;
}

• 三十题就留念，还不够别人的零头呢。。 (18) hzoi 2014-02-14 08:11:31