obsidian

POJ 2349 Arctic Network (Kruskal)

08
2017/08

# 题目

## 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 4
0 100
0 300
0 600
150 750

## Sample Output

212.13

# 题意

1、任意两个站点都可以联系（直接或者间接）；

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

# 思路

2、如果$u$,$v$不在同一个连通分量中,那么加入 $(u,v)$ 一定是最优解。

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

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

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

# 代码

#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;
{
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);
}
Kruskal(p);
printf("%.2f\n",ans[p-s-1]);
}
return 0;
}

# 总结

Last modification：November 2nd, 2019 at 02:29 pm