记录编号	83743	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	超级傲娇的AC酱	是否通过	通过
代码语言	C++	运行时间	1.616 s
提交时间	2013-12-06 11:06:21	内存使用	8.92 MiB

/*
DESIGNED BY CH
KRUSKAL+UFS
ON 2013/12/5 23:06
*/
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fi("wire.in");
ofstream fo("wire.out");
const int INF=0xffffff;
const int Len=1500+2;
int A[Len][Len],F[Len],n;
vector<pair<int,pair<int,int> > >E;
void init();
void Kruskal();
void Uion(int,int);
int Find(int);
int main()
{
	init();
	Kruskal();
	return 0;
}
void init(){int i,j;
	fi>>n;
	for(i=0;i<n;i++)for(j=0;j<n;j++)fi>>A[i][j];
	for(i=0;i<n;i++)A[i][i]=INF,F[i]=i;
	for(i=0;i<n;i++)for(j=0;j<i;j++)E.push_back(make_pair(A[i][j],make_pair(i,j)));
}
void Kruskal()
{
	int Ans=0,sum=0,pos_S,pos_E;
	sort(E.begin(),E.end());
	while(sum<E.size())
	{
		pos_S=E[sum].second.first;pos_E=E[sum].second.second;
		if(Find(pos_S)!=Find(pos_E)){
			Ans+=A[pos_S][pos_E];
			Uion(pos_S,pos_E);
		}
		sum++;
	}
	fo<<Ans;
}
void Uion(int x,int y){
	F[Find(x)]=Find(y);
}
int Find(int x){
	return F[x]==x?x:F[x]=Find(F[x]);
}