记录编号	408144	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	玉带林中挂	是否通过	通过
代码语言	C++	运行时间	2.643 s
提交时间	2017-05-23 20:14:14	内存使用	26.07 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int fa[1505];
struct Edge
{
	int from,to,cos;
}edge[2250005];
bool cmp(Edge a,Edge b)
{
	return a.cos<b.cos;
}

int find(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
int main()
{
	freopen("wire.in","r",stdin);
	freopen("wire.out","w",stdout);
	scanf("%d",&n);
	int po=0;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	  {
	  	int k=po++;
	  	edge[k].from=i;
	  	edge[k].to=j;
	  	scanf("%d",&edge[k].cos);
	  }
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(edge+1,edge+n*n+1,cmp);
	long int ans=0;
	for(int i=1;i<=n*n;i++)
	{
		int fx=find(edge[i].from),fy=find(edge[i].to);
		if(fx!=fy)
		{
			ans+=edge[i].cos;
			fa[fx]=fy;
		}
	}
	printf("%ld",ans);    
	fclose(stdin);
	fclose(stdout);
	return 0;
}