记录编号	231203	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	xbwcan	是否通过	通过
代码语言	C++	运行时间	2.873 s
提交时间	2016-02-25 19:16:28	内存使用	24.26 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INT=1500*1500+1;
int u[INT],v[INT],w[INT],n,f[1505],r[INT],cur,o=0;
bool cmp(const int i,const int j){return w[i]<w[j];}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int  Kruskal(){
	int  ans=0;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=cur;i++)r[i]=i;
	sort(r+1,r+1+cur,cmp);
	for(int i=1;i<=cur;i++){
		int e=r[i];
		int x=find(u[e]);int y=(find(v[e]));
		if(x!=y){
			ans+=w[e];
			f[x]=y;
			o++;
		}
		if(o==n-1)return ans;
	}
	return ans;
}
int main(){
	freopen("wire.in","r",stdin);
	freopen("wire.out","w",stdout);
	int x;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&x);
			if(i<j&&x>0){
				cur++;
				u[cur]=i,v[cur]=j,w[cur]=x;
			}
		}
	}
	int m=Kruskal();
	printf("%d",m);
	return 0;
}