Fork me on GitHub

POJ 2349 Arctic Network (Kruskal)

题目

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 \leq S \leq 100$, the number of satellite channels, and $S\leq P \leq 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
3
4
5
6
1
2 4
0 100
0 300
0 600
150 750

Sample Output

1
212.13

题意

有$P$个站点,每个站点之间都有权重(两点之间的距离),给出$S$个卫星,如果两个站点之间用卫星连接,那么它们之间的权值将变为 $0$ ,给出每个站点的坐标,需要保证:

1、任意两个站点都可以联系(直接或者间接);

2、使任意两站点的最大通信花费变得最小。

需要输出最大的通信花费。

思路

最小生成树的问题,利用 $Kruskal$ 算法,它的目的是建立一个最小生成树,但是模板中最后返回的是最小生成树的权值和。它的第一步是给所有边按照从小到大的顺序排列。这一步可以直接调用库函数 $qsort$ 或者 $sort$ 。记每条边为 $(u,v)$。
有两种情况:1、 $u$ 和 $v$ 在同一个连通分量中,加入 $(u,v)$ 会形成环,不能选择。
2、如果$u$,$v$不在同一个连通分量中,那么加入 $(u,v)$ 一定是最优解。
现在需要知道三件事:

1、在一张全联通图的最小生成树中,新增一条权为0的边,新增加的边则取代形成的环中的另外一条边形成新的最小生成树。

2、在一张全连通图中,若在其最小生成树中挑选 $S$ 个节点,在其两两间添加权为 $0$ 的边,则新生成的边必定可以取代生成的环中的 $S−1$ 个边构成新的最小生成树。选择 $S$ 个节点,得到的最小生成树由 $S-1$ 条权为 $0$ 的边构成,接下来将剩下的点加入最小生成树里,只需要添加 $(N-1)-(S-1)=N-S$ 条边。

3、在一张全连通图中,新增的一条边可以和任意一条边构成环。

于是,利用 $Kruskal$ 算法在求最小生成树的时候,如果 $u$ 和 $v$ 不在同一个连通分量里,那就通过 $pair$ 建立坐标将 $ans$ 放入 $vector$ 数组里,因为 $ans$ 在过程中已经是从小到大排好的,最后需要输出的就是 $ans[N-S-2]$ 。

代码

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
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
const double eps = 1e-6;
int fa[250005];
vector<double> ans;
void init(int n)
{
for(int i=0;i<=n;i++)
{
fa[i]=i;
}
}
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return ;
else
fa[x]=y;
}
bool same(int x,int y)
{
return find(x)==find(y);
}
vector <pair<double,PII> > G;
void add_egde(int u,int v,double d)
{
G.pb(mp(d,mp(u,v)));
}
void Kruskal(int n)
{
init(n);
sort(G.begin(),G.end());
int m=G.size();
int num=0;
for(int i=0;i<m;i++)
{
pair<double,PII> p=G[i];
int x=p.second.first;
int y=p.second.second;
double d=p.first;
if(!same(x,y))
{
unite(x,y);
num++;
ans.pb(d); //将边权放入vector中
}
if(num==n-1)
break;
}
}
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void joint(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
{
fa[x]=y;
}
}
int main()
{
int t;
cin>>t;
int s,p;
while(t--)
{
pair<double,double> P[505];
G.clear();
ans.clear();
cin>>s>>p;
for(int i=0;i<p;i++)
{
cin>>P[i].first>>P[i].second;
}
for(int i=0;i<p;i++)
for(int j=i+1;j<p;j++)
{
double d=dis(P[i].first,P[i].second,P[j].first,P[j].second);
add_egde(i,j,d);
add_egde(j,i,d);
}
Kruskal(p);
printf("%.2f\n",ans[p-s-1]);
}
return 0;
}

总结

自己理解好久以及在大佬的帮助下最终还是做出了,太菜了。。。

-------------本文结束感谢您的阅读-------------
obsidian wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持是我最大的动力!