试题描述：

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

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

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

输入：

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

输出：

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

输入示例：

1

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=9999999using 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<=p;i++)        min_line[i]=map[start][i];    for(int i=2;i<=p;i++)    {        double minn=9999999;        for(int j=2;j<=p;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<=p;j++)            if(book[j]==0)                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,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<=p;i++)            cin>>input[i].x>>input[i].y;        for(int i=1;i<=p;i++)            for(int j=1;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]=0;            }        prim();        sort(ltj,ltj+h,cemp);        //for(int i=1;i<=p;i++)            //cout<<min_line[i]<<" ";        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<=h-1; i++)           //printf("  %.2lf", ltj[i]);    }   // system("pause");}

View Code

给大家一组数据：

11 5009383 8862777 69157793 83355386 4926649 14212362 278690 597763 3926540 34269172 57365211 53682567 64295782 15302862 51234067 31353929 98024022 30583069 81671393 84565011 80426229 73734421 49193784 85375198 43248315 43706413 35266091 89809956 18736862 91706996 72812305 9257084 6327336 6505846 17291313 58576124 38959582 5458814 33675434 3644043 37501087 68087276 71785788 35845403 26512754 23999932 50609676 33687739 126226 85868094 7539795 5701434 3787467 660197 29023317 4926652 7567301 2804286 94413865 96898444 66198440 47298031 81178097 57714481 675709 89274567 78569497 23534586 69655306 46836219 86241528 28715732 88299503 198270 33689708 67156340 81497796 7232618 22452846 34512921 35552379 74887764 82289841 23505193 15007034 7764124 49146987 58563743 64912227 83659859 19361432 25516437 92283275 54071474 61218858 43956029 12378235 37935818 44286143 10115928 95298776 24044443 57634613 45388606 68402904 48185128 6887369 79179917 69963324 77439470 21838490 54999772 67255644 55907505 81392954 97867669 80828542 8464197 95079355 88046348 86113622 78289299 73435746 55684340 54223311 38107605 18015661 37304878 13059320 87369444 86268522 34656708 34168282 32582924 76372062 56242600 20363452 18999379 55507468 71973 71313881 49308933 58948660 1637199 79818899 29962959 37732813 96687190 10952926 64665084 13402090 76843376 55425936 91077445 97569179 84186887 94123348 21721659 20092336 52106342 75878206 93017713 73725321 12554819 45997721 99045939 98113940 56671705 62281127 91505984 66583920 92242422 72691396 40815630 849292 19727672 38507625 53851222 92996640 60423898 7132298 6190524 25908209 85818819 93367732 11555994 8004379 47695273 17768850 72551860 81425579 58841993 32057621 95672504 6131961 27541326 42598944 82023202 35066784 20212842 8689528 51898872 99089958 4988036 88087753 62483303 33332133 16482890 97547567 1746368 95294500 80463788 97976249 69903303 30335363 2497253 48927686 91251152 39965975 91889157 37295436 24603414 3921460 630428 80278050 67487556 89024794 76978699 10431039 2002428 64034500 6817647 85386159 51512535 21344339 16922215 6127504 562949 9648285 64295343 63353177 29005238 79716949 2895367 79882292 5795743 31442829 83901682 53403541 5693826 42322261 6042360 91178023 676181 63093190 54258996 63674677 4234690 16264524 60579614 31688205 3586312 73865100 43462726 49944916 65525578 35298946 22902647 69709051 90809631 8593857 86271312 18869214 83553512 904412 94799610 89696189 22746355 76416620 54338987 78888338 45667770 72846856 417606 22605849 2377205 30595217 85184945 7836873 8458873 76374289 4836607 4782757 93144471 57291100 34593618 94388025 13883074 12338157 36813493 358270 6993417 18395569 83632622 87943173 98476431 74626682 93904292 57915057 51151521 61578574 14911947 29519231 5021537 37405054 40304098 53251081 75163516 30022231 61391796 54042338 45809218 90213970 98624812 53794977 26851536 99044176 34839207 97594857 97443499 9911127 39505236 75607818 5105563 491244 87111805 99343291 73758955 36143589 37688993 49182805 68824822 69826717 40303093 1574126 65931486 253543 30747814 47138179 83774762 57757088 29195710 6732294 1017346 2351137 56915153 39432573 6328925 92916710 40187217 68366963 50557090 38588130 49048571 26619633 96854789 30732604 68519805 92507868 65039485 90062195 46392949 1120967 2266763 7677596 3981865 75609036 79557770 35189211 63422532 51962379 73218270 49844172 44274234 20407283 727398 58301063 3476950 2030573 37146059 75224047 69245082 94351232 92042954 4431898 54865640 42789159 2629262 96831041 98481723 83246272 91224154 73355821 74579365 27471171 1776269 52188701 17034653 9933907 39596728 28065797 87207084 13085334 2698991 63768898 27151052 51718189 15592506 40109016 82243109 65390 33788109 50535081 91141338 59899426 80675147 52236787 22316532 21221281 38754850 1796590 22545350 11313813 78571494 91816081 46035720 24337982 1817487 94159296 88255404 87226892 551297 329134 31818506 4157057 9708595 99991962 22977483 5776154 89771309 25879932 33825021 42663563 88603682 92117685 90864285 9305990 45837314 14764116 58201892 75255528 88397525 74901136 13609618 7643337 9286582 66214310 7955888 42256815 45703437 8538 77221783 23508657 90973827 91261269 20716651 3149910 528639 83981888 66102393 85773890 89765199 45526931 60878777 99657 8566952 70172641 27359368 12988184 31956776 58055266 34288954 2528308 95937278 21972555 9672774 64455000 2325997 82838412 61278382 5421结果是：
726.43

2349 Arctic Network（中文版）