记录编号	466728	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	小字、小瓶子	是否通过	通过
代码语言	C++	运行时间	1.380 s
提交时间	2017-10-29 16:09:50	内存使用	26.07 MiB

#include<iostream> 
#include<cstdio>
#include<algorithm>
const int maxn=2250000+5;
using namespace std;
struct nn{
	int x;
	int y;
	int w;
}np[maxn];
int h=0,f[1505];
int cmp(const nn &a,const nn &b)
{
	if(a.w<b.w) return 1;
	return 0;
}
//并查集
int found(int x)
{
	if(f[x]!=x) f[x]=found(f[x]);
	return f[x];
}
int unionn(int x,int y)
{
	x=found(x);
	y=found(y);
	f[y]=x;
}
//-----------
int main()
{
	freopen("wire.in","r",stdin);
	freopen("wire.out","w",stdout);
	int n,x,ans=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			scanf("%d",&x);
			if(j>i) 
			{
				np[h].x=i;
				np[h].y=j;
				np[h].w=x;
				h++;
			}
		}
	}
	for(int i=1;i<=n;i++)
		f[i]=i;
	sort(np,np+h,cmp);
	int i=0,k=0;
	while(i<h&&k<n)
	{
		if(found(np[i].x)!=found(np[i].y))
		{
			k++;
			ans+=np[i].w;
			unionn(np[i].x,np[i].y);
		}
		i++;
	}
	cout<<ans;
	return 0;
}