记录编号	405049	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.730 s
提交时间	2017-05-15 14:49:26	内存使用	0.32 MiB

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

const int MAXN = 1510;

inline int in(void){ 
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp)) tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

struct DATA{ 
	int a, b;
	int val;

	DATA(){;}

	DATA(int _a, int _b, int _val){ 
		a = _a, b = _b, val = _val;
	}

	bool operator < (const DATA& a) const { 
		return val < a.val;
	}
};

inline bool Union(int a, int b);
int Find(int a);

int fa[MAXN];
int N, n, cnt, min_cost;
vector<DATA> data;

int main(){ 
#ifndef LOCAL
	freopen("wire.in", "r", stdin);
	freopen("wire.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	n = N = in();

	for(int i = 1; i <= N; ++i) fa[i] = i;

	for(int i = 1, tmp; i <= N; ++i){ 
		for(int j = 1; j <= N; ++j){ 
			tmp = in();
			if(i >= j) continue;
			
			data.push_back(DATA(i, j, tmp));
		}
	}

	sort(data.begin(), data.end());

	while(n ^ 1 && cnt < data.size()){ 
		int a, b, c;
		do{ 
			a = data[cnt].a;
			b = data[cnt].b;
			c = data[cnt].val;
			++cnt;
		}while(!Union(a, b));

		min_cost += c;
		--n;
	}

	printf("%d\n", min_cost);

	return 0;
}

inline bool Union(int a, int b){ 
	int x = Find(a), y = Find(b);
	if(x == y) return false;
	fa[x] = y;
	return true;
}

int Find(int a){ 
	if(fa[a] != a) return fa[a] = Find(fa[a]);
	return a;
}