Arctic Network---poj2349 最小生成树

http://poj.org/problem?id=2349

题意：有n个点给出坐标，点和点之间可以用无线电或者卫星通信，每个点都有无线电收发器可进行无线电通信，但是只有m个点有卫星通信功能。卫星通信的距离可以无限大，但无线电通信的距离不能超过D，超过D的部分将使通信费用增加。要使通信费用最少。

其实就是求一次最小生成树，m个点有卫星通信，那么就会有m-1条边的通信距离无限大，其实就是这m-1条边不用计算费用。而剩下的边中，找出最大边作为D值，这样剩下的所有的边都不会大于D，那么不会增加通信费用。在构建MST过程中保存下所有的边权值，然后按升序排序，除掉最后的m-1条边（也就是最大的m-1条边，这些边用卫星通信），最大的那条就是D

d数组记录最小生成树的边；

#include<stdio.h>

#include<string.h>

#include<map>

#include<iostream>

#include<algorithm>

#include<math.h>

#define N 510

#define INF 0xfffffff

using namespace std;

struct node

{

    int x, y;

    double d;

}a[N],b[N*N];

int cmp(node p,node q)

{

    return p.d < q.d;

}

int f[N];

int Find(int x)

{

    if(x!=f[x])

        f[x] = Find(f[x]);

    return f[x];

}

int main()

{

    int T, m, n, i, j, k, p;

    double d[N*N];

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d", &m, &n);

        for(i=; i<=n; i++)

            f[i] = i;

        memset(a, , sizeof(a));

        memset(b, , sizeof(b));

        memset(d, , sizeof(d));

        for(i=; i<=n; i++)

            scanf("%d%d", &a[i].x, &a[i].y);

        k=;

        for(i=; i<=n; i++)

        {

            for(j=; j<i; j++)

            {

                b[k].x = i;

                b[k].y = j;

                b[k++].d = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));

            }

        }

        sort(b, b+k, cmp);

        p = ;

        for(i=; i<k; i++)

        {

            int px = Find(b[i].x);

            int py = Find(b[i].y);

            if(px!=py)

            {

                f[px] = py;

                d[p++] = b[i].d;

            }

        }

        printf("%.2f\n", d[p-m]);

    }

    return ;

}