记录编号	186929	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.562 s
提交时间	2015-09-16 08:41:23	内存使用	26.12 MiB

#include <cstdio>
#include <algorithm>
using namespace std;

struct edge{
	int u, v, t;
	bool operator < (const edge &rhs) const{
		return rhs.t > t;
	}
}E[1502*1502];

int n, m, f[1502];

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

int main()
{
	freopen("mcst.in", "r", stdin);
	freopen("mcst.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) f[i] = i;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++){
			int x;
			scanf("%d", &x);
			if (x > 0 && i < j) E[++m].u = i, E[m].v = j, E[m].t = x;
		}
	sort(E + 1, E + m + 1);
	int ans = 0, e = 0;
	for (int i = 1; i <= m; i++){
		int fu = find(E[i].u), fv = find(E[i].v);
		if (fu == fv) continue;
		f[fu] = fv;
		e++;
		ans += E[i].t;
		if (e == n - 1) {
			printf("%d", ans);
			return 0;
		}
	}
	printf("-1");
	return 0;
}