记录编号	188828	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	1.605 s
提交时间	2015-09-25 14:40:03	内存使用	46.12 MiB

#include <iostream>
#include <climits>
#include <fstream>
//#define self
#include <algorithm>
#include <cstdlib>

using namespace std;
const int MAXN(2001);
struct edge{
	int fr, to, v;
} e[((MAXN * (MAXN - 1) >> 1) + 1) * 2];

ifstream fin("wire.in");
ofstream fout("wire.out");
#define cin fin
#define cout fout
int n, ans = 0, ecnt = 0, fa[MAXN], ne = 0;
inline void kruskal(), uni(edge);
int me(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 (x != 0 && i < j){
				e[++ecnt].fr = i;
				e[ecnt].to = j;
				e[ecnt].v = x;
			}
		}
	
	kruskal();
	
	cout << ans;
	fin.close();
	fout.close();
#ifdef self
	system("fc wire.out wire.ans");
	for (; ; );
#endif
}

inline void kruskal(){
	for (int i = 1; i <= n; ++i)
		fa[i] = i;
	sort(e + 1, e + ecnt + 1, cmp);
	for (int i = 1; i <= ecnt; ++i){
		if (me(e[i].fr) != me(e[i].to))
			uni(e[i]);
		if (ne == n - 1)
			break;
	}
}

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

int me(int x)
{
	if (fa[x] != x)
		fa[x] = me(fa[x]);
	return fa[x];
}

inline void uni(edge y){
	int faa = me(y.fr), fab = me(y.to);
	if (faa != fab)
		fa[me(y.to)] = me(y.fr);
	ans += y.v;
	++ne;
}