#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct point 
{
	double x,y;
}p[111];
double dis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int rank[10001];
int v[10001];
void make_set(int x)
{
    v[x]=x;
    rank[x]=0;
}
int find_set(int x)
{
    if(v[x]!=x) v[x]=find_set(v[x]);
    return v[x];
}

void Union(int x,int y)
{
    if(rank[x]>rank[y])
        v[y]=x;
    else if(rank[x]<rank[y])
        v[x]=y;
    else if(rank[x]==rank[y])
    {
        v[x]=y;
        rank[y]++;
    }
}

struct Edge
{
 int x,y;
 double w;
}e[10001];
bool cmp(Edge e1,Edge e2)
{if(e1.w<e2.w) return true; else return false;}

int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
 int n,m,s1,s2; int i,j;
 double ans;
 scanf("%d",&n);
 for(i=0;i<n;i++)
	 scanf("%lf%lf",&p[i].x,&p[i].y);
 m=0;
 for(i=0;i<n;i++)
	 for(j=0;j<n;j++)
	{
		e[m].x=i;
		e[m].y=j;
		e[m].w=dis(p[i],p[j]);
		//printf("%lf\t",e[m].w);
		m++;	
	}

	
//	printf("%d\n",m);
 
 
 sort(e,e+m,cmp);
 for(i=0;i<n;i++) make_set(i);
 ans=0;
 for(i=0;i<m;i++)
	{
      s1=find_set(e[i].x); s2=find_set(e[i].y);
	  if(s1!=s2)
		{
		//  printf("%d %d",s1,s2);
	     ans+=e[i].w;
	     Union(s1,s2);
	    }
 
    }
 printf("%.2lf\n",ans);
return 0;
}

• Re:why WA?连Waterloo原来的数据都通过的了。。为什么还是错呢？查了半天也没找出来。。哪个大牛现身指点下小弟/? (22) xiaorong 2011-03-06 20:57:18