记录编号	380532	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.521 s
提交时间	2017-03-09 17:00:59	内存使用	26.14 MiB

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

int n, et, u[1503];
int rk[1510];

struct edge {
	int f,t;
	int w;
}e[1503 * 1501];

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

inline int read() {
	int k = 0, f = 1;
	char c = getchar();
	for(;!isdigit(c); c = getchar()) if(c == '-')f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}

int getf(int i) {
	if(u[i] == i)return i;
	else {
		u[i] = getf(u[i]);
		return u[i];
	}
}

void Kruscal() {
	
	for(int i = 1; i <= n; i++) {
		u[i] = i, rk[i] = 1;
	}
	int maxn = 0;
	for(int i = 0; i <= et; i++) {
		int x = getf(e[i].f);
		int y = getf(e[i].t);
		if(x == y)continue;
		else {
			maxn += e[i].w;
			if (rk[x] == rk[y]) u[y] = x, rk[x]++;
			else if (rk[x] < rk[y]) u[x] = y;
			else u[y] = x;
		}
	}
	
	printf("%d",maxn);
	
}

int main() {
#ifndef LOCAL
	freopen("mcst.in", "r", stdin);
	freopen("mcst.out", "w", stdout);
#endif
	n = read();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			int w = read();
			if(w == -1)continue;
			else {
				e[et].f = i;
				e[et].t = j;
				e[et++].w = w;
//				e[et++].f = j;
//				e[et].t = i;
//				e[et].w = w;
			}
		}
	}
	
//	for(int i = 1; i <= et; i++){
//		printf("%d -> %d  cost %d\n", e[i].f, e[i].t, e[i].w);
//	}
	
	sort(e, e + et, cmp);
	
//	for(int i = 0; i < et; i++){
//		printf("%d -> %d  cost %d\n", e[i].f, e[i].t, e[i].w);
//	}
	
	Kruscal();
	
	
}