Arctic Network---poj2349 最小生成树

题意：有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=0; i<=n; i++)
            f[i] = i;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(d, 0, sizeof(d));
        for(i=1; i<=n; i++)
            scanf("%d%d", &a[i].x, &a[i].y);
        k=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; 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 = 0;
        for(i=0; 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
", d[p-m]);
    }

    return 0;
}

Arctic Network---poj2349 最小生成树

相关推荐