P1991 无线通讯网[MST]

题目描述

国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络；

每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。

任意两个配备了一条卫星电话线路的哨所（两边都ᤕ有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。

收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距离 D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

输入格式

从 wireless.in 中输入数据第 1 行，2 个整数 S 和 P，S 表示可安装的卫星电话的哨所数，P 表示边防哨所的数量。接下里 P 行，每行两个整数 x，y 描述一个哨所的平面坐标(x, y)，以 km 为单位。

输出格式

输出 wireless.out 中

第 1 行，1 个实数 D，表示无线电收发器的最小传输距离，精确到小数点后两位。

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

212.13

说明/提示

对于 20% 的数据：P = 2，S = 1

对于另外 20% 的数据：P = 4，S = 2

对于 100% 的数据保证：1 ≤ S ≤ 100，S < P ≤ 500，0 ≤ x，y ≤ 10000。

思路

　　建图算出点之间距离跑kruskal，满足可以通信的站点数就是总数 - 卫星通话的站点数

ＣＯＤＥ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 using namespace std;
  8 const int maxn = 2e5+7;
  9 
 10 ///把所有边排序，记第i小的边为:e[i](1 <= i < m)
 11 ///初始化MST为空
 12 ///初始化连通分量，让每个点自成一个独立的连通分量
 13 ///for(int i = 0; i < m; i++) {
 14 ///   if(e[i].u 和 e[i].v 不在同一个连通分量) {
 15 ///     把边e[i]加入MST
 16 ///     合并e[i].u 和 e[i].v 所在的连通分量
 17 ///   }
 18 ///}
 19 
 20 int fa[5050],n,m,ans,eu,ev,cnt;
 21 
 22 struct node{
 23     int u, v;
 24     double w;
 25 }e[maxn];
 26 
 27 struct Node {
 28     double x,y;
 29 }a[maxn];
 30 
 31 bool cmp(node a, node b)
 32 {
 33     return a.w < b.w;
 34 }
 35 
 36 int fid(int x)
 37 {
 38     return x == fa[x] ? x : fid(fa[x]);
 39 }
 40 
 41 void init(int n)
 42 {
 43     for(int i = 1; i <= n; i++) {
 44         fa[i] = i;
 45     }
 46     ans = 0;
 47     cnt = 0;
 48 }
 49 
 50 bool unite(int r1, int r2)///冰茶鸡
 51 {
 52     int fidroot1 = fid(r1), fidroot2 = fid(r2);
 53     if(fidroot1 != fidroot2) {
 54         fa[fidroot2] = fidroot1;
 55         return true;
 56     }
 57     return false;
 58 }
 59 
 60 void kruskal(int n,int s,int m)
 61 {
 62     sort(e+1, e+m+1, cmp);
 63     for(int i = 1; i <= m; i++) {
 64         eu = fid(e[i].u);
 65         ev = fid(e[i].v);
 66         if(eu == ev) {
 67             continue;
 68         }
 69         ans += e[i].w;
 70         fa[ev] = eu;
 71         //printf("cnt:%d n-s:%d\n",cnt+1,n-s);
 72         if(++cnt == n-s) {
 73             printf("%.2f\n",e[i].w);
 74             break;
 75         }
 76     }
 77 }
 78 
 79 int main()
 80 {
 81     int t;
 82     t = 1;
 83     while(t--) {
 84         int s,n;
 85         scanf("%d %d",&s,&n);
 86         for(int i = 1; i <= n; i++) {
 87             scanf("%lf %lf",&a[i].x,&a[i].y);
 88         }
 89         int num = 1;
 90         for(int i = 1; i <= n; i++) {
 91             for(int j = i+1; j <= n; j++) {
 92                 e[num].u = i, e[num].v = j;
 93                 e[num].w = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
 94                 num++;
 95             }
 96         }
 97         /*for(int i = 1; i <= num; i++) {
 98             printf("e[%d]:%lf\n",i,e[i].w);
 99         }*/
100         num--;
101         init(n);
102         kruskal(n,s,num);
103     }
104     return 0;
105 }

View Code