记录编号	191451	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.755 s
提交时间	2015-10-07 19:14:14	内存使用	34.09 MiB

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
const int MAXN(1052);
struct edge{
	int fr, to, w;
}	e[MAXN * MAXN << 1];

ifstream fin("mcst.in");
ofstream fout("mcst.out");
#define cin fin
#define cout fout
int n, ecnt = 0, ans = 0, f[MAXN * MAXN << 1], cnt = 0, ufs(int);
bool cmp(const edge, const edge);

main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j){
			int x;
			cin >> x;
			if (i <= j && x != -1){
				e[++ecnt].fr = i;
				e[ecnt].to = j;
				e[ecnt].w = x;
			}
		}
	fin.close();
	
	sort(e + 1, e + ecnt + 1, cmp);
	for (int i = 1; i <= ecnt; ++i)
		f[i] = i;
	for (int i = 1; i <= ecnt; ++i){
		if (ufs(e[i].fr) != ufs(e[i].to)){
			f[f[e[i].fr]] = f[e[i].to];
			ans += e[i].w;
			++cnt;
		}
		if (cnt >= n - 1)
			break;
	}
	
	cout << ans;
	fout.close();
//	for (; ; );
}

bool cmp(const edge a, const edge b)
{
	return a.w < b.w;
}

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