直到敲完这个题，我才发现原来prim如果用邻接矩阵存图即使加上堆优化时间复杂度依然是O(n2)qwq……
首先，由于两个点只需要间接联通就可以互相通讯，所以这道题可以用最小生成树去做。这一步比较好完成。
问题在于怎么去加卫星电话。
由于两个点只要间接联通就可以，那么每一个用无线电收发器连成的子图只需要有一个卫星电话即可与其它的点联通，所以我们在删边的时候需要先判断一下这两个点删完边以后是不是仍然联通而不是傻傻地给这两个点都安装上卫星电话（被这个卡了好久qwq）
![]()
如图所示，由于2、4号点都安装了电话，所以删掉边1-3后，1、3号点之间就不需要安装电话的。
再来看如何安装电话。
![]()
如图，我们可以发现，当前两个点安装完卫星电话以后，每一个子图都会拥有一个卫星电话。当我们继续删边时，分成的两个新的子图都是一个有卫星电话，一个没有，所以我们从第二次开始每次删边只需要增加一部卫星电话即可。所以最终留下的最大的边是第s大的边（由于第一次删边你需要安装两台卫星电话，所以你最多只能删s - 1条边）
附一下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define INF 0x7fffffff
#define re register
using namespace std;
int read()
{
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
struct NODE{
int x, y, num;
double minn;
}a[1000];
int s,p,vis[1000],del[1000],fa[1000],f[1000];
struct node{
int k;
double dis;
bool operator < ( const node &x )const{return x.dis < dis;}
};
priority_queue <node> que;
int mysort(NODE a, NODE b){return a.minn > b.minn;}
int main()
{
s = read(); p = read();
for(re int i = 1; i <= p; i++)
{
a[i].x = read();
a[i].y = read();
a[i].num = i;
}
for(re int i = 1; i <= p; i++) a[i].minn = INF;
que.push((node){1,0});
vis[1] = 1;a[1].minn = 0;
while(!que.empty())
{
node now = que.top();
que.pop();
vis[now.k] = 1;
for(re int i = 1; i <= p; i++)
{
if(!vis[i] && sqrt((a[now.k].x - a[i].x) * (a[now.k].x - a[i].x) + ((a[now.k].y - a[i].y) * (a[now.k].y - a[i].y))) < a[i].minn)
{
a[i].minn = sqrt((a[now.k].x - a[i].x) * (a[now.k].x - a[i].x) + ((a[now.k].y - a[i].y) * (a[now.k].y - a[i].y)));
que.push((node){i,a[i].minn});
fa[i] = now.k;
}
}
}
sort(a + 1, a + p + 1, mysort);
int j = 1;
double Min = a[j].minn;
Min = a[s].minn;
printf("%.2lf\n",Min);
return 0;
}
|
