记录编号	227248	评测结果	AAAAWWWWWA
题目名称	通信线路	最终得分	50
用户昵称	Hzoi_Go灬Fire	是否通过	未通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-02-18 15:55:08	内存使用	0.69 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=200;
struct Node
{
	int from,to,dis;
};
Node a[maxn*maxn];
int n,ans=0,root[maxn],len=0,tt=0;
void Init();
void Insert(int,int,int);
int Kruskal();
int Findroot(int);
bool Comp(const Node&a,const Node&b)
{
	if(a.dis<b.dis)return 1;
	else return 0;
}
int main()
{
    freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	Init();
	return 0;
}

void Init()
{
	memset(a,0,sizeof(a));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		root[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int x;
			scanf("%d",&x);
			if(x==-1)Insert(i,j,0x7f7f7f7f);
			else Insert(i,j,x);
		
		}
	}
	int ans=Kruskal();
	printf("%d",ans);
	//return;
}
void Insert(int x,int y,int z)
{
	len++;
	a[len].from=x;
	a[len].to=y;
	a[len].dis=z;
}
int Kruskal()
{
	sort(a+1,a+len+1,Comp);
	/*for(int i=1;i<=n*n;i++)
	{
		cout<<a[i].dis<<" "<<endl;
	}*/
	for(int i=1;i<=len;i++)
	{
		int x=a[i].from,y=a[i].to;
		int rx=Findroot(x),ry=Findroot(y);
		if(rx==ry)continue;
		else 
		{
			root[rx]=ry;
			ans+=a[i].dis;
			tt++;
			if(tt==n-1)break;
		}		
	}
	return ans;
}
int Findroot(int x)
{
	if(root[x]!=x)
	{
		root[x]=Findroot(root[x]);
	}
	return root[x];
}