记录编号	406561	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	据说这是zzy	是否通过	通过
代码语言	C++	运行时间	1.470 s
提交时间	2017-05-18 21:24:30	内存使用	17.52 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,g=0,gg=0;
struct edge
{
    int u,v;
    double w;
}e[1127252];
int father[1502];
void CSH()//初始化并查集的祖先为自己
{
    for(int i=0;i<=n;i++)
        father[i]=i;
}
 int findme(int x) //并查集的查找即寻根操作（带路径压缩）
{
    if(father[x]!=x)
        father[x]=findme(father[x]);
    return father[x];
}
void hebing(int x,int y)//并查集的合并操作
{
    int xm=findme(x);
    int ym=findme(y);
    if(xm!=ym)
        father[ym]=xm;
}
bool cmp(const edge &a,const edge &b)
{
    return a.w<b.w;
}
int main()
{
	freopen("mcst.in","r",stdin);
    freopen("mcst.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			cin>>gg;
			if(j>i&&gg!=-1)
			{
				e[g].u=i;
				e[g].v=j;
				e[g].w=gg;
				g++;
			}
		}
    sort(e+0,e+g,cmp);
    int cntedge=0,rootu,rootv;
    double s=0;
    CSH();
    for(int i=0;i<g;i++)
    {
        rootu=findme(e[i].u);
        rootv=findme(e[i].v);
        if(rootu!=rootv)
        {
            s+=e[i].w;
            cntedge++;
            hebing(e[i].u,e[i].v);//合并集合
        }
		if(cntedge==n-1)
            break;
    }
    cout<<s<<endl;
	return 0;
}