POJ - 2349 ZOJ - 1914 Arctic Network 贪心+Kru
2024-08-24 03:22:37
Arctic Network
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.
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
题意:有S颗卫星和P个哨所,有卫星的两个哨所之间可以任意通信;否则,一个哨所只能和距离它小于等于D的哨所通信。给出卫星的数量和P个哨所的坐标,求D的最小值。
分析:这是一个最小生成树问题。P个哨所最多用P-1条边即可连起来,而S颗卫星可以代替S-1条边,基于贪心思想,代替的边越长,求得的D就越小。所以可以用一个数组保存加入最小生成树的边的长度,共有P-1条边,把前S-1条较长的边代替掉,剩下的边中最长的即为所求,所以Kru加边至第(P-1)-(S-1)=P-S条边即为所求。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std; int f[],x[],y[]; struct Node{
int u,v;
double w;
}edge[]; bool cmp(Node a,Node b)
{
return a.w<b.w;
} int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
} double kru(int s,int n,int m)
{
int i;
for(i=;i<=n;i++){
f[i]=i;
}
sort(edge+,edge+m+,cmp);
int cnt=;
double ans=;
for(i=;i<=m;i++){
int u=edge[i].u;
int v=edge[i].v;
double w=edge[i].w;
int fu=find(u),fv=find(v);
if(fu!=fv){
ans=w;
f[fv]=fu;
cnt++;
}
if(cnt==n-s) break;
}
if(cnt<n-s) return -;
else return ans;
} int main()
{
int t,s,n,m,i,j;
scanf("%d",&t);
while(t--){
scanf("%d%d",&s,&n);
for(i=;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
memset(edge,,sizeof(edge));
int m=;
for(i=;i<=n;i++){
for(j=i+;j<=n;j++){
edge[++m].w=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
edge[m].u=i;
edge[m].v=j;
}
}
printf("%.2f\n",kru(s,n,m));
}
return ;
}
最新文章
- ITTC数据挖掘平台介绍(四) 框架改进和新功能
- OO基本原则
- win10 服务(系统默认服务)注册表
- NS2中修改载波侦听范围和传输范围
- c++ basic 整理1
- Windows环境下32位汇编语言程序设计(典藏版)
- Redhat6.5 安装64位oracle11.2.0.1
- 翻译:Knockout 快速上手 - 3: knockoutJS 快速上手
- 在xml中调用自己用java代码定义的View
- TChromeTabs 使用日记
- 使用SqlBulkCopy类批量复制大数据
- NLS_COMP和NLS_SORT参数
- HTML5本地存储详解
- 【Storm】Storm实战之频繁二项集挖掘
- dubbo 笔记-XML配置文件简介
- Spring IOC容器分析(1) -- BeanFactory
- 【实验吧】CTF_Web_简单的SQL注入之1
- Dynamics CRM2016 Web API之更新记录
- 微信分享JS-SDK
- Dubbo常用配置文件分析及核心源码阅读(SPI.Extension)