记录编号	31303	评测结果	AAATTTTTTA
题目名称	通信线路	最终得分	40
用户昵称	TBK	是否通过	未通过
代码语言	C++	运行时间	9.004 s
提交时间	2011-11-02 10:22:49	内存使用	0.32 MiB

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
struct fun
{
	int x;
	int y;
	int z;
}f[1501];
int a,b,c,d,l,m,n,r[1501]={0},s;
int Compare(const void *elem1,const void *elem2)
{
	struct fun *elem3=(struct fun *)elem1;
	struct fun *elem4=(struct fun *)elem2;
	return (elem3->x > elem4->x) ?1:-1;
}
int main(void)
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	scanf("%d",&b);
	l=0;
	for (c=0;c<b;c++)
		for (d=0;d<b;d++)
		{
			scanf("%d",&a);
			if (d<c) continue;
			if (a!=-1) 
			{
				f[l].x=a;
				f[l].y=c;
				f[l].z=d;
				l++;
			}
		}
	qsort(f,l,sizeof(fun),Compare);
	m=1;
	s=f[0].x;
	r[f[0].y]=m;
	r[f[0].z]=m;
	for (c=1;c<l;c++)
	{
		if ((r[f[c].y]==0)&&(r[f[c].z]==0)) 
		{
			m++;
			r[f[c].y]=m;
			r[f[c].z]=m;
			s+=f[c].x;
		}
			else if ((r[f[c].y]==0)&&(r[f[c].z]!=0)) 
				 {
					r[f[c].y]=r[f[c].z];
					s+=f[c].x;
				 }
					else if ((r[f[c].y]!=0)&&(r[f[c].z]==0)) 
						 {
							r[f[c].z]=r[f[c].y];
							s+=f[c].x;
						 }
							else if (r[f[c].y]!=r[f[c].z])
								 {
									n=r[f[c].z];
									for (d=0;d<b;d++)
										if (r[d]==n) r[d]=r[f[c].y];
									s+=f[c].x;
								 }
	}
	printf("%d\n",s);
	fclose(stdin);
	fclose(stdout);
	return(0);
}