zoj 1914 Arctic Network

找最小生成树的倒数第几长边的问题

1，读入数据的处理，最终处理为结构体形式

2，快排................................

3，并查集找结点，并记录边长大小

4，输出所求数据

<span style="font-size: 18px;">#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef struct Tedge
{
    int from,to;
    int dist;
}edge;

edge dis[500*500];           //记录from点到to点的距离
int  ans[500+10];         //记录距离
int coor[510][5];         //记录各个点的坐标
int fa[500+10];            //定义father域


int D(int x)              //计算一个数的平方
{
    return(x*x);
}


int P(int i,int j)        //计算两个点之间的距离的平方
{
    return( D(coor[i][0]-coor[j][0])+D(coor[i][1]-coor[j][1]) );
}

int cmp(const void *a,const void *b)
{
   return (*(edge *)a).dist - (*(edge *)b).dist;
}


int find(int i)
{
    if(fa[i] == i)return i;
    fa[i]=find(fa[i]);
    return fa[i];
}
 
int main()
{
    int N,s,p,i,j;
    int n = 0;                    //记录各个点之间的距离数
    scanf("%d",&N);
    while(N--)
    {
        scanf("%d%d",&s,&p);
        for(i=1;i<=p;i++)
          scanf("%d%d",&coor[i][0],&coor[i][1]);        //读入了各点坐标
       
        n = 0;
        for(i=1;i<=(p-1);i++)
        {
           for(j=i+1;j<=p;j++)
           {
              dis[n].from = i;
              dis[n].to   = j;
              dis[n].dist = P(i,j);
              n++;
           }
        }                                     //求出了各点之间的距离
       
        qsort(dis,n,sizeof(edge),cmp);           //对dis结构体数组排序
       
        for(i=1;i<=p;i++)fa[i]=i;
        int total = 0;
        for(i=0;i<n;i++)
        {
             if(find(dis[i].from) != find(dis[i].to))
             {
                  fa[ fa[dis[i].from] ]  =  fa[dis[i].to];
                total++;
                ans[total] = dis[i].dist;
                if(total == (p-s))break;
             }
        }
        printf("%.2lf\n",sqrt(ans[total]));
       
    }
    return 0;
}
</span>