学步园

UVA_10397

    这个题目是一个求最小生成树的题目，只不过在求最小生成树之前要先用并查集对已经建好的边进行处理即可。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
double x[1010],y[1010],w[1000010];
int u[1000010],v[1000010],p[1010],r[1000010];
int cmp(const void *_p,const void *_q)
{
int *p=(int *)_p;
int *q=(int *)_q;
return w[*p]>w[*q]?1:-1;
}
double distance(int i,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));    
}
int find(int x)
{
return p[x]==x?x:(p[x]=find(p[x]));    
}
int main()
{
int i,j,k,n,N,M,e,tx,ty,a,b;
double ans;
while(scanf("%d",&N)==1)
    {
for(i=0;i<N;i++)
            scanf("%lf%lf",&x[i],&y[i]);
        n=0;
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
            {
                u[n]=i;
                v[n]=j;
                w[n]=distance(i,j);
                n++;
            }
for(i=0;i<n;i++)
            r[i]=i;
        qsort(r,n,sizeof(r[0]),cmp);
for(i=0;i<N;i++)
            p[i]=i;
        scanf("%d",&M);
for(i=0;i<M;i++)
        {
            scanf("%d%d",&a,&b);
            a--;
            b--;
            tx=find(a);
            ty=find(b);
if(tx!=ty)
                p[tx]=ty;
        }
        ans=0.0;
for(i=0;i<n;i++)
        {
            e=r[i];
            tx=find(u[e]);
            ty=find(v[e]);
if(tx!=ty)
            {
                p[tx]=ty;
                ans+=w[e];
            }
        }
        printf("%.2f\n",ans);
    }
return 0;    
}