無線通訊網_紀中3078_最小生成樹

Description

國防部計劃用無線網絡連接配接若幹個邊防哨所。2種不同的通訊技術用來搭建無線網絡：每個邊防哨所都要配備無線電收發器；有一些哨所還可以增配衛星電話。

任意兩個配備了一條衛星電話線路的哨所均可以通話，無論它們相距多遠。而隻通過無線電收發器通話的哨所之間的距離不能超過D，這是受收發器的功率限制。收發器的功率越高，通話距離D會更遠，但同時價格也更貴。

收發器需要統一購買和安裝，是以全部哨所隻能選擇安裝一種型号的收發器。換句話說，每一對哨所之間的通話距離都是同一個D。

你的任務是确定收發器必須的最小通話距離D，使得每一對哨所之間至少有一條通話路徑(直接的或者間接的)。

Input

第1行：2個整數S(1 <= S <= 100)和P(S < P <= 500)，S表示可安裝的衛星電話的線路數，P表示邊防哨所的數量。

接下來P行，每行描述一個哨所的平面坐标(x,y)，以km為機關，整數，0<=x,y<=10,000

Output

第1行：1個實數D，表示無線電收發器的最小傳輸距離。精确到小數點後2位。

Analysis

圖論專題于是想到了最小生成樹，

統計一下兩兩之間的點的距離排序，并查集判斷是否在同一個集合，kruskal一下就能過了

因為題目有n次免費機會，是以隻用找到m-n條邊就可以退了，由于邊有序，是以免費靠後的邊是最優的

還有就是，洛谷有原題;-b

Code

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct edge
{
    int x,y;
    double w;
};
edge e[];
int x[],y[],f[];
int maxE=;
double dist(int a,int b)
{
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
void add(int x,int y,double w)
{
    e[++maxE]=(edge){x,y,w};
}
bool cmp(edge x,edge y)
{
    return x.w<y.w;
}
int find(int x)
{
    if (!f[x])
        return x;
    f[x]=find(f[x]);
    return f[x];
}
void merge(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if (a!=b)
        f[a]=b;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=;i<=m;i++)
        scanf("%d%d",&x[i],&y[i]);

    for (int i=;i<=m-;i++)
        for (int j=i+;j<=m;j++)
            add(i,j,dist(i,j));
    sort(e+,e+maxE+,cmp);

    double ans=;
    int k=;
    for (int i=;i<=maxE;i++)
        if (k<m-n)
        {
            int a=find(e[i].x),b=find(e[i].y);
            if (a!=b)
            {
                k++;
                ans=e[i].w;
                merge(a,b);
            }
        }
    printf("%.2f\n",ans);
    return ;
}