POJ 2349 Arctic Network（最小生成树，第k大边权，基础）

浏览数：19 / 时间：2015年06月09日

/*********题意解说——来自discuss——by sixshine**************/

有卫星电台的城市之间可以任意联络。没有卫星电台的城市只能和距离小于等于D的城市联络。
题目告诉你卫星电台的个数S，让你求最小的D.
做最小生成树，去掉最长的S条边后，剩下最长的边就是D.
也就是求最小生成树中第S+1长的边。
完毕。

/********************************************************/

//听说听木看懂之后，数据很水，果然能水过
#define  _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;

#define M 510
#define inf 999999999
double mat[M][M],keep[M];
struct tt
{
    double x,y;
}d[M];

int m;

double prim(int n,int sta)
{
    double sum=0.0,dis[M];
    int mark[M],i,j,s=0;
    for(i=0;i<n;i++)
    {
        dis[i]=mat[sta][i];
        mark[i]=0;
    }
    mark[sta]=1;
    for(i=1;i<n;i++)
    {
        double minn=inf*1.0;
        int flag=-1;
        for(j=0;j<n;j++)
        {
            if(minn>dis[j]&&mark[j]==0)
            {
                flag=j;
                minn=dis[j];
            }
        }
        keep[s++]=dis[flag];
        mark[flag]=1;
        sum+=dis[flag];
        for(j=0;j<n;j++)
        {
            if(dis[j]>mat[flag][j])
                dis[j]=mat[flag][j];
        }
    }
    sort(keep,keep+n-1);
    return keep[n-m-1];
}


int main()
{
    int t,i,j,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&d[i].x,&d[i].y);
            for(j=0;j<i;j++)
            {
                mat[i][j]=mat[j][i]=sqrt((d[i].x-d[j].x)*(d[i].x-d[j].x)+(d[i].y-d[j].y)*(d[i].y-d[j].y));
            }
        }
        memset(keep,0,sizeof(keep));
        printf("%.2lf\n",prim(n,0));
    }
    return 0;
}