Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出n个点坐标。。。然后可以建s个卫星基站。。。有卫星基站的地方之间可以互相免费通信。。现在要建一些无线电通讯线路（不同于卫星基站，是另一种通信方式），两个点之间线路的代价是他们的距离。。。问最小距离是多少。。。使得任意两个点之间都可以直接或者间接联系。。。
思路：mst即可。。。s个卫星基站可以减少s-1条最大的边。。。多组数据。。m忘记清0.。。re一发。。。2a
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月13日 星期三 16时35分42秒
4File Name :code/poj/2349.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=505;
34int n,s;
35int m;
36int f[N];
37struct Edge
38{
39 int u,v;
40 double w;
41
42 bool operator < (Edge b)const
43 {
44 return w<b.w;
45 }
46}edge[N*N];
47struct point
48{
49 double x,y;
50
51 void input()
52 {
53 scanf("%lf%lf",&x,&y);
54 }
55
56 double dis( point b)
57 {
58 double res = 0 ;
59 res = (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
60 return sqrt(res);
61 }
62}p[N];
63
64void init()
65{
66 for ( int i = 1 ; i <= n ; i++) f[i] = i;
67}
68
69int root ( int x)
70{
71 if (x!=f[x]) f[x] = root (f[x]);
72 return f[x];
73}
74
75void merge( int x,int y)
76{
77 int rx = root(x);
78 int ry = root(y);
79 if (rx==ry) return;
80 f[rx] = ry;
81}
82int main()
83{
84#ifndef ONLINE_JUDGE
85 freopen("code/in.txt","r",stdin);
86#endif
87
88 int T;
89 cin>>T;
90 while (T--)
91 {
92 scanf("%d%d",&s,&n);
93 init();
94 for ( int i = 1 ; i <= n ; i++) p[i].input();
95
96 m = 0;
97 for ( int i = 1 ; i <= n ; i++)
98 for ( int j = 1 ; j <= n ; j++)
99 if (i<j)
100 {
101 m++;
102 edge[m].u = i;
103 edge[m].v = j;
104 edge[m].w = p[i].dis(p[j]);
105 }
106
107 sort(edge+1,edge+m+1);
108
109 int cnt = 0 ;
110 double ans;
111 for ( int i = 1 ; i <= m ; i++)
112 {
113 int u = edge[i].u;
114 int v = edge[i].v;
115 double w = edge[i].w;
116 if (root(u)==root(v)) continue;
117 merge(u,v);
118 ans = w;
119 cnt++;
120 if (cnt>=n-s) break;
121 }
122
123 printf("%.2f\n",ans);
124 }
125
126#ifndef ONLINE_JUDGE
127 fclose(stdin);
128#endif
129 return 0;
130}