2349 Arctic Network（中文版）

试题描述：

国防部希望通过无线网络连接几个北方前哨基地。在建立网络时将使用两种不同的通信技术：每个前哨基站都将拥有无线电收发器，另外还有一些前哨卫星通道。

任何带卫星频道的两个前哨都可以通过卫星进行通信，无论其位置如何。否则，只有两个前哨基站之间的距离不超过D，才能通过无线电通信，这取决于收发器的功率。更高的功率产生更高的D，但成本更高。由于采购和维护的考虑，前哨收发器必须相同; 也就是说，D的价值对于每对前哨都是一样的。

您的工作是确定收发器所需的最小D。在每对前哨之间必须至少有一条通信路径（直接或间接）。

输入：

第一行输入包含N个测试用例数。每个测试用例的第一行包含1 <= S <= 100，卫星通道数，S <P <= 500，前哨数。遵循P行，给出每个前哨的（x，y）坐标，单位为km（坐标为0和10,000之间的整数）。

输出：

对于每种情况，输出应由一条线组成，给出连接网络所需的最小D。输出应指定为2个小数点。

输入示例：

2 4

0 100

0 300

0 600

150 750

输出示例：

212.3

题解：

这道题所用的是最小生成树+贪心。

我所用的是最小生成树的prim。

prim是什么可以百度。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <cmath>

#define MAXN=9999999

using namespace std;

double map[][],min_line[];

double ltj[];

bool book[];

int s,p,h;

struct big_tree

{

    double x,y;

}input[];

double ojld(double x1,double y1,double x2,double y2)

{

    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));

}

void prim()

{

    int start;

    start=;

    h=;

    book[start]=;

    for(int i=;i<=p;i++)

        min_line[i]=map[start][i];

    for(int i=;i<=p;i++)

    {

        double minn=;

        for(int j=;j<=p;j++)

            if(book[j]== && minn>min_line[j])

            {

                minn=min_line[j];

                start=j;

            }

        ltj[h++]=minn;

        book[start]=;

        for(int j=;j<=p;j++)

            if(book[j]==)

                min_line[j]=min(min_line[j],map[start][j]);

    }

}

bool cemp(double a,double b)

{

   return a<b;

}

double mmaaxx(double a,double b)

{

    if(a>b)

        return a;

    else

        return b;

}

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        memset(map,,sizeof(map));

        memset(book,,sizeof(book));

        memset(min_line,,sizeof(min_line));

        memset(ltj,,sizeof(ltj));

        cin>>s>>p;

        for(int i=;i<=p;i++)

            cin>>input[i].x>>input[i].y;

        for(int i=;i<=p;i++)

            for(int j=;j<=p;j++)

            {

                if(i!=j)

                {

                    map[i][j]=ojld(input[i].x,input[i].y,input[j].x,input[j].y);

                    map[j][i]=map[i][j];

                }

                if(i==j)

                    map[i][j]=;

            }

        prim();

        sort(ltj,ltj+h,cemp);

        //for(int i=1;i<=p;i++)

            //cout<<min_line[i]<<" ";

        for(int i=p;i>p-s+;i--)

            min_line[i]=;

        double ans=;

        printf("%0.2f\n",ltj[h--s+]);

        //for(int i=1; i<=h-1; i++)

           //printf("  %.2lf", ltj[i]);

    }

   // system("pause");

}

给大家一组数据：

秒客网

2349 Arctic Network（中文版）

相关文章