记录编号	126311	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.943 s
提交时间	2014-10-11 23:54:05	内存使用	7.14 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <vector>
#include <queue>
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("wire.in", "r");
FILE *out = fopen("wire.out", "w");
#endif
#define maxn (1502)
inline void getint(int &t){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	t = c - '0';
	while(isdigit(c = fgetc(in)))t = t * 10 - '0' + c;
}
using namespace std;
int G[maxn][maxn], ans = 0, low[maxn];
bool inS[maxn] = {1};
int main(){
	int n, i, j;
	getint(n);
	for(i = 0;i < n; ++i)for(j = 0;j < n; ++j)
			getint(G[i][j]);
	for(i = 0;i < n; ++i)
		low[i] = G[0][i];
	for(i = 1;i < n; ++i){
		int Min = 0x7fffffff, pos;
		for(j = 0;j < n; ++j) if(!inS[j] && low[j] < Min)
			Min = low[j], pos = j;
		ans += Min;
		inS[pos] = 1;
		for(j = 0;j < n; ++j) if(!inS[j] && G[pos][j] < low[j])
			low[j] = G[pos][j];
	}
	fprintf(out, "%d\n", ans);
	return 0;
}