文章目录
  1. 1. 原题重现
    1. 1.1. Description
    2. 1.2. Input
    3. 1.3. Output
    4. 1.4. Sample Input
    5. 1.5. Sample Output
  2. 2. 解题思路
    1. 2.1. 题意
    2. 2.2. 思路
  3. 3. 代码

引言:这道题虽然是简单的最小生成树问题,但实在很有意思,比较考验思考与猜想能力。我在一开始也确实没搞明白这其中的奥妙。


原题重现

Description

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.

Input

	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).

Output

	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

	1
	2 4
	0 100
	0 300
	0 600
	150 750

Sample Output

	212.13

解题思路

题意

这道题是说有PP个站点,都有收发器,其中SS个还额外有卫星可以随便分配,有卫星的站点之间通信花费为00,其他站点通信花费与两点间的距离相同。现在给出每个点的坐标,要保证:

  1. 任意两站点可直接或间接通信。
  2. 要使任意两点间最大通信花费最小。

求满足上述两个条件的花费。

思路

这最小生成树的问题,使用克鲁斯卡尔算法(Kruskal\mathbb{Kruskal}),贪心找出连通PP个站点的P1P-1条边,满足条件11

要满足条件22,因为两个装着卫星的站点可以00花费,也就是消去一条边的花费,所以考虑这SS个卫星怎么分配的问题十分关键。

生成树

首先我们要证明:

  1. 在一张全连同图的最小生成树中,新增一条权为00的边,新增加的边则取代形成的环中的另外一条边形成新的最小生成树。
  2. 在一张全连通图中,若在其最小生成树中挑选SS个节点,在其两两间添加权为00的边,则新生成的边必定可以取代生成的环中的S1S-1个边构成新的最小生成树。
  3. 在一张全连通图中,新增的一条边可以和任意一条边构成环。

第一个很好想明白,最小生成树只需要保留可以把N个节点连接好的N1N-1条边就行了,因为是之前是全连通的,再加一条边,肯定可以形成一个环,去掉环中的一条边就可以构成新的最小生成树了。

第二个也很好理解,根据Kruskal\mathbb{Kruskal}算法,我是贪心得到构不成环的尽可能多的边,那么我先贪权为0的边,假设我挑选SS个节点,先在这些节点构建最小树,得到的最小生成树由S1S-1条权为00的边构成,接下来我需要将剩下的点加进最小生成树里,添加NSN-S条边就可以了。

第三个想一下就清楚了。

整理一下思路,就是说我们这SS个节点如果选的好,就可以刚好与原本最小树里最长的S1S-1条边构成环,将其取代掉即可,且必定能够存在这种情况。

于是代码思路是:

  1. 求出最小生成树,假设存在w数组中,下标范围是0N20 \sim N-2
  2. 求出max(w0,w1,w2,...,wNS1)max(w_0,w_1,w_2,...,w_{N-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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define MOD (ll)(1e9+7)
inline int read()
{
int a = 0, f = 1; char c = getchar();
while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
while (isdigit(c)) (a *= 10) += c - '0', c = getchar();
return a*f;
}
inline ll read2()
{
ll a = 0, f = 1; char c = getchar();
while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
while (isdigit(c)) (a *= 10) += c - '0', c = getchar();
return a*f;
}

struct node{int u,v;double w;};
struct coo{int x,y;double s;};
vector<node> vec;
vector<coo> co;
vector<node> v;
int a[505];
int Find(int n);
void joint(int x,int y);
double dist(coo a,coo b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp(node a,node b)
{
return a.w<b.w;
}
int main(void)
{
int N=read();
while(N--)
{
int S=read(),P=read();
co.clear();
vec.clear();
v.clear();
for(int i=0;i<P;i++)
{
a[i]=i;
int u=read(),v=read();
co.push_back(coo{u,v,0});
}
for(int i=0;i<P;i++)
for(int j=i+1;j<P;j++)
vec.push_back(node{i,j,dist(co[i],co[j])});
sort(vec.begin(),vec.end(),cmp);
int len=vec.size();
int cnt=0;
for(int i=0;cnt<P-1;i++)
{
if(Find(vec[i].u)!=Find(vec[i].v))
{
joint(vec[i].u,vec[i].v);
cnt++;
v.push_back(vec[i]);
}
}
double maxn=0;
for(int i=P-S-1;i>=0;i--)
{
maxn=max(maxn,v[i].w);
}
printf("%.2f\n",maxn);

}
return 0;
}

int Find(int n)
{
int i=n;
while(a[i]!=i)
{
i=a[i];
}
int t;
while(a[n]!=i)
{
t=a[n];
a[n]=i;
n=t;
}
return i;
}
void joint(int x,int y)
{
int tx=Find(x),ty=Find(y);
if(tx!=ty)
a[tx]=ty;
}
文章目录
  1. 1. 原题重现
    1. 1.1. Description
    2. 1.2. Input
    3. 1.3. Output
    4. 1.4. Sample Input
    5. 1.5. Sample Output
  2. 2. 解题思路
    1. 2.1. 题意
    2. 2.2. 思路
  3. 3. 代码