2349 Arctic Network(中文版)

时间:2022-10-13 12:26:48

试题描述:

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

任何带卫星频道的两个前哨都可以通过卫星进行通信,无论其位置如何。 否则,只有两个前哨基站之间的距离不超过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=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");
}

给大家一组数据:

1
1 500
9383 886
2777 6915
7793 8335
5386 492
6649 1421
2362 27
8690 59
7763 3926
540 3426
9172 5736
5211 5368
2567 6429
5782 1530
2862 5123
4067 3135
3929 9802
4022 3058
3069 8167
1393 8456
5011 8042
6229 7373
4421 4919
3784 8537
5198 4324
8315 4370
6413 3526
6091 8980
9956 1873
6862 9170
6996 7281
2305 925
7084 6327
336 6505
846 1729
1313 5857
6124 3895
9582 545
8814 3367
5434 364
4043 3750
1087 6808
7276 7178
5788 3584
5403 2651
2754 2399
9932 5060
9676 3368
7739 12
6226 8586
8094 7539
795 570
1434 378
7467 6601
97 2902
3317 492
6652 756
7301 280
4286 9441
3865 9689
8444 6619
8440 4729
8031 8117
8097 5771
4481 675
709 8927
4567 7856
9497 2353
4586 6965
5306 4683
6219 8624
1528 2871
5732 8829
9503 19
8270 3368
9708 6715
6340 8149
7796 723
2618 2245
2846 3451
2921 3555
2379 7488
7764 8228
9841 2350
5193 1500
7034 7764
124 4914
6987 5856
3743 6491
2227 8365
9859 1936
1432 2551
6437 9228
3275 5407
1474 6121
8858 4395
6029 1237
8235 3793
5818 4428
6143 1011
5928 9529
8776 2404
4443 5763
4613 4538
8606 6840
2904 4818
5128 688
7369 7917
9917 6996
3324 7743
9470 2183
8490 5499
9772 6725
5644 5590
7505 8139
2954 9786
7669 8082
8542 8464
197 9507
9355 8804
6348 8611
3622 7828
9299 7343
5746 5568
4340 5422
3311 3810
7605 1801
5661 3730
4878 1305
9320 8736
9444 8626
8522 3465
6708 3416
8282 3258
2924 7637
2062 5624
2600 2036
3452 1899
9379 5550
7468 71
973 7131
3881 4930
8933 5894
8660 163
7199 7981
8899 2996
2959 3773
2813 9668
7190 1095
2926 6466
5084 1340
2090 7684
3376 5542
5936 9107
7445 9756
9179 8418
6887 9412
3348 2172
1659 2009
2336 5210
6342 7587
8206 9301
7713 7372
5321 1255
4819 4599
7721 9904
5939 9811
3940 5667
1705 6228
1127 9150
5984 6658
3920 9224
2422 7269
1396 4081
5630 84
9292 1972
7672 3850
7625 5385
1222 9299
6640 6042
3898 713
2298 6190
524 2590
8209 8581
8819 9336
7732 1155
5994 8004
379 4769
5273 1776
8850 7255
1860 8142
5579 5884
1993 3205
7621 9567
2504 613
1961 2754
1326 4259
8944 8202
3202 3506
6784 2021
2842 868
9528 5189
8872 9908
9958 498
8036 8808
7753 6248
3303 3333
2133 1648
2890 9754
7567 1746
368 9529
4500 8046
3788 9797
6249 6990
3303 3033
5363 2497
253 4892
7686 9125
1152 3996
5975 9188
9157 3729
5436 2460
3414 3921
460 6304
28 8027
8050 6748
7556 8902
4794 7697
8699 1043
1039 2002
428 6403
4500 681
7647 8538
6159 5151
2535 2134
4339 1692
2215 6127
504 5629
49 964
8285 6429
5343 6335
3177 2900
5238 7971
6949 289
5367 7988
2292 5795
743 3144
2829 8390
1682 5340
3541 569
3826 4232
2261 6042
360 9117
8023 6761
81 6309
3190 5425
8996 6367
4677 4234
690 1626
4524 6057
9614 3168
8205 358
6312 7386
5100 4346
2726 4994
4916 6552
5578 3529
8946 2290
2647 6970
9051 9080
9631 8593
857 8627
1312 1886
9214 8355
3512 90
4412 9479
9610 8969
6189 2274
6355 7641
6620 5433
8987 7888
8338 4566
7770 7284
6856 417
606 2260
5849 237
7205 3059
5217 8518
4945 783
6873 8458
873 7637
4289 483
6607 478
2757 9314
4471 5729
1100 3459
3618 9438
8025 1388
3074 1233
8157 3681
3493 358
270 699
3417 1839
5569 8363
2622 8794
3173 9847
6431 7462
6682 9390
4292 5791
5057 5115
1521 6157
8574 1491
1947 2951
9231 5021
537 3740
5054 4030
4098 5325
1081 7516
3516 3002
2231 6139
1796 5404
2338 4580
9218 9021
3970 9862
4812 5379
4977 2685
1536 9904
4176 3483
9207 9759
4857 9744
3499 9911
127 3950
5236 7560
7818 5105
563 49
1244 8711
1805 9934
3291 7375
8955 3614
3589 3768
8993 4918
2805 6882
4822 6982
6717 4030
3093 1574
126 6593
1486 253
543 3074
7814 4713
8179 8377
4762 5775
7088 2919
5710 6732
294 1017
346 235
1137 5691
5153 3943
2573 6328
925 9291
6710 4018
7217 6836
6963 5055
7090 3858
8130 4904
8571 2661
9633 9685
4789 3073
2604 6851
9805 9250
7868 6503
9485 9006
2195 4639
2949 1120
967 226
6763 7677
596 3981
865 7560
9036 7955
7770 3518
9211 6342
2532 5196
2379 7321
8270 4984
4172 4427
4234 2040
7283 72
7398 5830
1063 347
6950 2030
573 3714
6059 7522
4047 6924
5082 9435
1232 9204
2954 443
1898 5486
5640 4278
9159 262
9262 9683
1041 9848
1723 8324
6272 9122
4154 7335
5821 7457
9365 2747
1171 1776
269 5218
8701 1703
4653 9933
907 3959
6728 2806
5797 8720
7084 1308
5334 2698
991 6376
8898 2715
1052 5171
8189 1559
2506 4010
9016 8224
3109 6539
0 3378
8109 5053
5081 9114
1338 5989
9426 8067
5147 5223
6787 2231
6532 2122
1281 3875
4850 179
6590 2254
5350 1131
3813 7857
1494 9181
6081 4603
5720 2433
7982 181
7487 9415
9296 8825
5404 8722
6892 551
297 32
9134 3181
8506 415
7057 9708
595 9999
1962 2297
7483 5776
154 8977
1309 2587
9932 3382
5021 4266
3563 8860
3682 9211
7685 9086
4285 930
5990 4583
7314 1476
4116 5820
1892 7525
5528 8839
7525 7490
1136 1360
9618 7643
337 928
6582 6621
4310 7955
888 4225
6815 4570
3437 853
8 7722
1783 2350
8657 9097
3827 9126
1269 2071
6651 3149
910 528
639 8398
1888 6610
2393 8577
3890 8976
5199 4552
6931 6087
8777 99
657 8566
952 7017
2641 2735
9368 1298
8184 3195
6776 5805
5266 3428
8954 2528
308 9593
7278 2197
2555 9672
774 6445
5000 2325
997 8283
8412 6127
8382 5421
结果是:
726.43