记录编号	472790	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	东林桂香	是否通过	通过
代码语言	C++	运行时间	1.175 s
提交时间	2017-11-07 20:59:48	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct Ha{
	int u,v,lon;
};
vector<Ha>ha;
int n,x,ans=0,fa[1505];
bool cmp(Ha a,Ha b){return a.lon<b.lon;}
int kuai(){
	int x=0;char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
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);
	n=kuai();
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++){
	  	x=kuai();
	  	if(i<j){
	  		Ha ppp;ppp.u=i;ppp.v=j;ppp.lon=x;
	  		ha.push_back(ppp);
		}
	  }
	sort(ha.begin(),ha.end(),cmp);
	int pos=0;
	for(int i=0;i<ha.size();i++){
		int p=find(ha[i].u),q=find(ha[i].v);
		if(p!=q){
			fa[p]=q;
			ans+=ha[i].lon;
			pos++;
		}
		if(pos>=n-1)break;
	}
	printf("%d",ans);
	return 0;
}