记录编号	46774	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	1.125 s
提交时间	2012-10-29 18:43:41	内存使用	29.07 MiB

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("mcst.in");
ofstream fout("mcst.out");
const int MaxN=1502,MaxE=2253002;
int Index,N,M,Sum;
class Edge
{
public:
	int U,V,W;
}E[MaxE];
class UnionFindSet
{
public:
	int Prev;
}UFS[MaxN];
int find(int pos)
{
	if(UFS[pos].Prev!=pos)
		UFS[pos].Prev=find(UFS[pos].Prev);
	return UFS[pos].Prev;
}
void Union(int a,int b)
{
	UFS[b].Prev=a;
}
bool Cmp(Edge a,Edge b)
{
	return a.W < b.W;
}
void Add(int u,int v,int w)
{
	Index++;
	E[Index].U=u;E[Index].V=v;E[Index].W=w;
}
void Initialize()
{
int i,j,C;
	fin>>N;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
		{
			fin>>C;
			if(j<=i)
				continue;
			if(C!=-1)
				Add(i,j,C);
		}
}

void Kruscal()
{
int i;
	sort(E+1,E+Index+1,Cmp);
	for(i=1;i<=N;i++)
		UFS[i].Prev=i;
	for(i=1;i<=Index;i++)
	{
	int Ra=find(E[i].U),Rb=find(E[i].V);
		if(Ra!=Rb)
		{
			Sum+=E[i].W;
			Union(Ra,Rb);
		}
	}
	fout<<Sum<<endl;
}

int main()
{
	Initialize();
	
	Kruscal();
	
	fin.close();
	fout.close();
	return 0;
}