记录编号	541006	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	tat	是否通过	通过
代码语言	C++	运行时间	1.518 s
提交时间	2019-09-03 20:19:03	内存使用	22.26 MiB

#include <bits/stdc++.h>
using namespace std;
int n,ed[1501][1501]={0},f[1501]={0},ans=0;
struct eds{
	int a,b,d;
	bool operator <(const eds &r) const{
		return this->d > r.d;
	}
};
priority_queue<eds> q;
int fi(int x){
	if(x==f[x])return x;
	return f[x]=fi(f[x]);
}
int main(int argc, char** argv) {
	freopen("wire.in","r",stdin);
	freopen("wire.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&ed[i][j]);
			if(j<i){
				eds s;
				s.a=i;
				s.b=j;
				s.d=ed[i][j];
				q.push(s);
			}
		}
	}
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	int xxx=0; 
	while(!q.empty()){
		eds x=q.top();
		q.pop();
		int aa=x.a;
		int bb=x.b;
		int y1=fi(aa);
		int y2=fi(bb);
		if(f[y1]==f[y2]){
			continue;
		}
		xxx++;
		
		int dd=x.d;
		f[y1]=y2;
		ans+=dd;
		if(xxx==(n-1)){
			break;
		}
	}
	cout<<ans;
	return 0;
}