记录编号	403061	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	小字、小瓶子	是否通过	通过
代码语言	C++	运行时间	0.579 s
提交时间	2017-05-09 01:00:03	内存使用	13.21 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct DATA{
	int x;
	int y;
	int data;
}noip[1125751];
int noi[1502];
int sum;
int find(int m)
{
	if(noi[m]!=m)
		return noi[m]=find(noi[m]);
	return m;
}
void unionn(int r1,int r2)
{
	r1=find(r1);
	r2=find(r2);
	noi[r1]=r2;
}
int mycmp(const DATA &a,const DATA &b)
{
	if(a.data<b.data)
		return 1;
	return 0;
}
int main()
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	int n,t=0,c=0,d,m=0;
	cin>>n;
	for(int i=0;i<n;i++)
		noi[i]=i;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			scanf("%d",&d);
			if(j>i&&d!=-1)
			{
				noip[t].x=i;
				noip[t].y=j;
				noip[t].data=d;
				t++;
			}
		}
	}
	sort(noip+0,noip+t,mycmp);
	while(c<n-1)
	{
		if(find(noip[m].x)!=find(noip[m].y))
		{
			
			unionn(noip[m].x,noip[m].y);
			sum+=noip[m].data;
			
			c++;
		}
		m++;
	}
	cout<<sum;
	return 0;
}