UVa 10369 Arctic Network

浏览数：15 / 时间：2015年06月09日

Problem C: Arctic Network

The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.

Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed D, which depends of the power of the transceivers. Higher power yields higher D but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of D is the same for every pair of outposts.

Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000). For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.

Sample Input

Sample Output

212.13

也是最小生成树问题，与UVa 10397(http://www.cnblogs.com/lzj-0218/p/3571562.html)相似。

这个题中说，有此前哨之间可以通过卫星设施相互通信而无需考虑两点之间的距离，设有x部卫星通信设施，则可以在用Kruskal求完最小生成树之后，将求出的边从大到小减去(x-1)条边，余下的就是需要用radio transceiver通信的了

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<cmath>
  5 #include<vector>
  6 #define MAX_V 505
  7 
  8 using namespace std;
  9 
 10 typedef struct
 11 {
 12     int x;
 13     int y;
 14 } POINT;
 15 
 16 typedef struct
 17 {
 18     int s;
 19     int e;
 20     double dis;
 21 } CABLE;
 22 
 23 struct cmp
 24 {
 25     bool operator()(CABLE a,CABLE b)
 26     {
 27         return a.dis>b.dis;
 28     }
 29 };
 30 
 31 int V,E;
 32 int par[MAX_V];
 33 POINT p[MAX_V];
 34 double G[MAX_V][MAX_V];
 35 
 36 double Distance(POINT a,POINT b)
 37 {
 38     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 39 }
 40 
 41 void Initial()
 42 {
 43     for(int i=1;i<=V;i++)
 44         par[i]=i;
 45 }
 46 
 47 int Find(int x)
 48 {
 49     if(par[x]==x)
 50         return x;
 51     return par[x]=Find(par[x]);
 52 }
 53 
 54 bool Unite(int x,int y)
 55 {
 56     int par_x=Find(x);
 57     int par_y=Find(y);
 58     if(par_x!=par_y)
 59     {
 60         par[par_y]=par_x;
 61         return true;
 62     }
 63     return false;
 64 }
 65 
 66 int main()
 67 {
 68     int kase;
 69 
 70     scanf("%d",&kase);
 71 
 72     while(kase--)
 73     {
 74         scanf("%d %d",&E,&V);
 75         for(int i=1;i<=V;i++)
 76             scanf("%d %d",&p[i].x,&p[i].y);
 77 
 78         priority_queue<CABLE,vector<CABLE>,cmp> q;
 79 
 80         for(int i=1;i<=V;i++)
 81             for(int j=i+1;j<=V;j++)
 82             {
 83                 G[i][j]=Distance(p[i],p[j]);
 84                 CABLE temp;
 85                 temp.s=i;
 86                 temp.e=j;
 87                 temp.dis=G[i][j];
 88                 q.push(temp);
 89             }
 90 
 91         int total=0;
 92         Initial();
 93         double ans[MAX_V];
 94 
 95         while(total<V-1)
 96         {
 97             CABLE temp=q.top();
 98             q.pop();
 99             if(Unite(temp.s,temp.e))
100                 ans[total++]=temp.dis;
101         }
102 
103         total-=E;
104 
105         printf("%.2lf\n",ans[total]);
106     }
107 
108     return 0;
109 }