[FZOJ1489] 无线通讯网

2014-07-07
竞赛题解 / 图论
FJSCFZOJ最小生成树

描述 Description

国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。

任意两个配备了一条卫星电话线路的哨所（两边都拥有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。

收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 D。

你的任务是确定收发器必须的最小通话距离 D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

输入格式 InputFormat

第 1 行：2 个整数 S（1<=S<=100）和 P（S

接下里 P 行，每行描述一个哨所的平面坐标（x,y），以 km 为单位，整数，0<=x,y<=10000。

输出格式 OutputFormat

第 1 行：1 个实数 D，表示无线电收发器的最小传输距离。精确到小数点后两位。

样例输入 SampleInput

2 4
0 100
0 300
0 600
150 750

样例输出 SampleOutput

212.13

数据范围和注释 Hint

对于 20% 的数据 P=2，S=1.
对于另外 20% 的数据 P=4，S=2.
对于 100% 的数据 1<=S<=100，S<P<=500.

来源 Source

FJSC 图论测试

FZOJ 1489

代码 Code

MST.

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct point
{
    int z,y,x;
}a[505];
struct edge
{
    int l,r;
    double s;
    bool operator < (const edge &temp) const
    {
        return s<temp.s;
    }
}e[500005];
int fa[505];
int i,j,t,n,m,k,p,q;
double ans;
inline double dis(int l,int r)
{
    return sqrt((double)(a[l].x-a[r].x)*(a[l].x-a[r].x)+(a[l].y-a[r].y)*(a[l].y-a[r].y));
}
inline int getfa(int s)
{
    if (s==fa[s]) return s;
    fa[s]=getfa(fa[s]);
    return fa[s];
}
int main()
{
    freopen("wireless.in","r",stdin);
    freopen("wireless.out","w",stdout);
    scanf("%d%d",&n,&p);
    for (i=1;i<=p;i++) scanf("%d%d",&a[i].x,&a[i].y);
    if (n>=p)
    {
        printf("%.2lf",0);
        return 0;
    }
    for (i=1;i<=p;i++) fa[i]=i;
    m=0;
    for (i=1;i<=p;i++) for (j=1;j<=p;j++) if (i!=j) e[++m].l=i,e[m].r=j,e[m].s=dis(i,j);
    sort(e+1,e+m+1);
    t=0;
    for (i=1;i<=m;i++) if (getfa(e[i].l)!=getfa(e[i].r))
    {
        t++;
        ans=e[i].s;
        fa[getfa(e[i].l)]=e[i].r;
        if (t==p-n) break;
    }
    printf("%.2lf\n",ans);
    return 0;
}