记录编号	27299	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	201101	是否通过	通过
代码语言	C++	运行时间	1.373 s
提交时间	2011-09-07 19:17:56	内存使用	43.26 MiB

#include <stdio.h>
using namespace std;
int bcj[1501],bcnext[1501],bclen[1501],bchead[1501],bctail[1501],map[1501][1500][2],num[1501],sorted[2253001],posi[2253001],posj[2253001];
void swap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
void qqsort(int l,int r)
{
	int ll,rr,temp;
	ll=l;
	rr=r;
	temp=sorted[(l+r)/2];
	while (ll<=rr)
	{
		while (sorted[ll]<temp)
			ll++;
		while (sorted[rr]>temp)
			rr--;
		if (ll<=rr)
		{
			swap(sorted[ll],sorted[rr]);
			swap(posi[ll],posi[rr]);
			swap(posj[ll],posj[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(l,rr);
	if (ll<r)
		qqsort(ll,r);
}
void bcassign(int n)
{
	int i;
	for (i=0;i<=n-1;i++)
	{
		bcj[i]=i;
		bcnext[i]=-1;
		bclen[i]=1;
		bchead[i]=i;
		bctail[i]=i;
	}
}
void unionit(int jihe,int jihe2)
{
	int temp;
	temp=bchead[jihe2];
	bcnext[bctail[jihe]]=bchead[jihe2];
	while (temp)
	{
		bcj[temp]=jihe;
		temp=bcnext[temp];
	}
	bctail[jihe]=bctail[jihe2];
	bclen[jihe]+=bclen[jihe2];
}
int main(void)
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	int i,j,n,n2=0,n2flag=-1,temp,jihe,jihe2,total=0;
	bool done=true;
	scanf("%d",&n);
	for (i=0;i<=n-1;i++)
		for (j=0;j<=n-1;j++)
		{
			scanf("%d",&temp);
			if (j>=i)
				continue;
			if (temp==-1)
				continue;
			map[i][num[i]][0]=j;
			map[i][num[i]][1]=temp;
			num[i]++;
			posi[n2]=i;
			posj[n2]=j;
			sorted[n2]=temp;
			n2++;
		}
	qqsort(0,n2-1);
	bcassign(n);
	for (temp=1;temp<=n-1;temp++)
	{
		for (n2flag+=1;n2flag<=n2-1;n2flag++)
		{
			jihe=bcj[posi[n2flag]];
			jihe2=bcj[posj[n2flag]];
			if (jihe!=jihe2)
				break;
		}
		if (n2flag>n2-1)
		{
			done=false;
			break;
		}
		if (bclen[jihe]>bclen[jihe2])
			unionit(bcj[jihe],bcj[jihe2]);
		else
			unionit(bcj[jihe2],bcj[jihe]);
		total+=sorted[n2flag];
	}
	if (done)
		printf("%d\n",total);
	else
		printf("-1\n");
	fclose(stdin);
	fclose(stdout);
	return(0);
}