2349 Arctic Network（中文版）

2021-06-22 18:06

阅读：542

标签：book 网络输出 ios max soft int std art

试题描述：

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

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

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

输入：

第一行输入包含N个测试用例数。每个测试用例的第一行包含1

输出：

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

输入示例：

2 4

0 100

0 300

0 600

150 750

输出示例：

212.3

题解：

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

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

prim是什么可以百度。

#include 
#include 
#include 
#include 
#include 
#include #define MAXN=9999999
using namespace std;
double map[1010][1010],min_line[100010];
double ltj[100100];
bool book[100010];
int s,p,h;
struct big_tree
{
    double x,y;
}input[10010];
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=1;
    h=0;
    book[start]=1;
    for(int i=2;i)
        min_line[i]=map[start][i];
    for(int i=2;i)
    {
        double minn=9999999;
        for(int j=2;j)
            if(book[j]==0 && minn>min_line[j])
            {
                minn=min_line[j];
                start=j;
            }
        ltj[h++]=minn;
        book[start]=1;
        for(int j=2;j)
            if(book[j]==0)
                min_line[j]=min(min_line[j],map[start][j]);
    }        
}
bool cemp(double a,double b)
{
   return ab;
}
double mmaaxx(double a,double b)
{
    if(a>b)
        return a;
    else
        return b;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(map,250,sizeof(map));
        memset(book,0,sizeof(book));
        memset(min_line,0,sizeof(min_line));
        memset(ltj,0,sizeof(ltj));
        cin>>s>>p;
        for(int i=1;i)
            cin>>input[i].x>>input[i].y;
        for(int i=1;i)
            for(int j=1;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]=0;
            }
        prim();
        sort(ltj,ltj+h,cemp);
        //for(int i=1;i//cout
        for(int i=p;i>p-s+1;i--)
            min_line[i]=0;
        double ans=0;
        printf("%0.2f\n",ltj[h-2-s+2]);
        //for(int i=1; i//printf("  %.2lf", ltj[i]);
    }
   // system("pause");
}

View Code

给大家一组数据：

2349 Arctic Network（中文版）

标签：book 网络输出 ios max soft int std art

原文地址：http://www.cnblogs.com/jason2003/p/7169145.html

上一篇：Vuejs——组件——props数据传递

下一篇：C# 通知机制 IObserver<T> 和 IObservable<T>

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：2349 Arctic Network（中文版）
文章链接：http://soscw.com/essay/97493.html

亲，登录后才可以留言！

2349 Arctic Network（中文版）

评论

热门文章

推荐文章

最新文章

置顶文章