秒懂算法 | 无线网络

简介: 高级数据结构算法实例分析

640.jpg

01、实例分析:人工湖公路

问题描述:

东南亚发生了一场地震,ICPC组织通过计算机建立的无线网络遭到毁灭性的影响——网络中所有的计算机都损坏了。在陆续维修计算机之后,无线网络又逐渐开始运作。由于硬件的制约,每两台计算机只有保持不超过d米的距离,才可以直接进行通信。但是每台计算机又可以作为其他两台计算机通信的中介点,也就是说,假设A计算机与B计算机不在能直接通信的范围内,但是它们可以通过同时能与A和B计算机通信的C计算机建立间接通信关系。

在维修过程中,维修者可以进行两种操作: 维修一台计算机或者检测两台计算机之间是否能够通信。你的任务就是解答每一次的检测操作。

输入:

第一行包含两个整数N和d(1≤N≤1001,0≤d≤20000)。N表示计算机的数量,计算机编号从1开始到N,d为两台能直接通信的计算机所需保持距离的最大值。在接下来的N行,每行包含两个整数xi,yi(0≤xi,yi≤10000),表示N台计算机的坐标。接下来的一系列的输入都表示维修者的操作,每种操作都是以下两种中的一种。

  1. "O p" (1≤p≤N),表示维修第p台计算机。

  2. "S p q" (1≤p,q≤N), 表示检测p与q计算机是否能够通信。

输入不超过300000 行。

输出:

对于每组检测操作,若两台计算机能进行通信,则输出SUCCESS,否则输出FAIL。

输入样例:

4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4

输出样例:


FAIL
SUCCESS

解题思路:

(1) 本题的基本解题方法是通过并查集划分集合,根据每对点(每对计算机)的从属关系判断点(计算机)是否连通(通信)。

(2) 需根据计算机的通信范围确定每对计算机是否可以直接通信。

(3) 需注意的是,必须保证可以进行通信的每对计算机是完好无损的。

本题只要能正确建图(建立计算机间是否通信的关系),再通过并查集的知识就可以解题了,注意初始时每台计算机都是损坏的。解题步骤如下。

(1) 输入每个点的坐标后,首先根据计算机的通信范围建立每对计算机的连通关系。

(2) 当输入的操作为维修时,就将本台计算机标记为完好的,并将其与所有与其可以通信的且完好的计算机进行并操作,那么可通信的计算机都在同一棵树中,具有相同的根结点。

(3) 当输入的操作为询问时,若两台计算机具有相同的根结点,则可通信,否则不可通信。

参考程序:

#include<stdlib.h>
#include<math.h>
int map[1005][1005];
int mul(int x)
//求平方数的函数
return x *x;
int f[1005];int find(int x)
if(f[x]!=x)f[x]=find(f[x]);return f[x];
void make(int a,int b)
int fl=find(a);
int f2=find(b);if(f1!=f2)
f[f2]=f1;
void check(int a,int b)
//检验 a 与 b 是否连通并输出的函数
int fl=find(a);int f2=find(b);if(fl==f2)
printf("SUCCESS\n");return ;
printf("FAIL\n");
int main()
int n,flag[1005];
//flag 数组用于标记计算机是否完好
double d;
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag)) ;
scanf("号d号lf",&n,&d) ;
int x[1005],y[1005],i,j,k;for(i=1;i<=n;i++)
scanf("号d%d",&x[i],&y[il);for(i=l;i<=n;i++)
f[i]=i;for(i=1;i<n;i++)
//用两层 for 循环对可直接通信的两台计算机进行标记
for(j=i+1;j<=n;j++)if(sqrt((double) (mul(x[i]-x[j]) +mul(y[il-y[j]) ))<=d)
map[i][j]=1;
map[j][i]=1;
char s[5];
int a,b;
while(scanf("s",s)!=EOF)
if(strcmp(s,"O")== 0)
scanf("d",&a);flag[a]=1;for(i=l;i<=n;i++)if(map[illal&&flag[i])//将可直接通信的并且完好的计算机合并为同一个集合make(a,i);
else
scanf("各d号d",&a,&b);check(a,b);
//判断并输出结果
目录
相关文章
|
1月前
|
机器学习/深度学习 算法 调度
14种智能算法优化BP神经网络(14种方法)实现数据预测分类研究(Matlab代码实现)
14种智能算法优化BP神经网络(14种方法)实现数据预测分类研究(Matlab代码实现)
207 0
|
1月前
|
机器学习/深度学习 并行计算 算法
粒子群算法优化RBF神经网络的MATLAB实现
粒子群算法优化RBF神经网络的MATLAB实现
289 123
|
19天前
|
机器学习/深度学习 算法
采用蚁群算法对BP神经网络进行优化
使用蚁群算法来优化BP神经网络的权重和偏置,克服传统BP算法容易陷入局部极小值、收敛速度慢、对初始权重敏感等问题。
161 5
|
28天前
|
存储 算法 安全
即时通讯安全篇(三):一文读懂常用加解密算法与网络通讯安全
作为开发者,也会经常遇到用户对数据安全的需求,当我们碰到了这些需求后如何解决,如何何种方式保证数据安全,哪种方式最有效,这些问题经常困惑着我们。52im社区本次着重整理了常见的通讯安全问题和加解密算法知识与即时通讯/IM开发同行们一起分享和学习。
174 9
|
4月前
|
机器学习/深度学习 算法 数据挖掘
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
|
4月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本内容包含基于BiLSTM与遗传算法(GA)的算法介绍及实现。算法通过MATLAB2022a/2024b运行,核心为优化BiLSTM超参数(如学习率、神经元数量),提升预测性能。LSTM解决传统RNN梯度问题,捕捉长期依赖;BiLSTM双向处理序列,融合前文后文信息,适合全局信息任务。附完整代码(含注释)、操作视频及无水印运行效果预览,适用于股票预测等场景,精度优于单向LSTM。
|
1月前
|
算法 数据挖掘 区块链
基于遗传算法的多式联运车辆路径网络优优化研究(Matlab代码实现)
基于遗传算法的多式联运车辆路径网络优优化研究(Matlab代码实现)
|
1月前
|
机器学习/深度学习 传感器 算法
【表面粗糙度】基于粒子群PSO算法优化-BP神经网络的表面粗糙度研究(Matlab代码实现)
【表面粗糙度】基于粒子群PSO算法优化-BP神经网络的表面粗糙度研究(Matlab代码实现)
169 7
|
1月前
|
机器学习/深度学习 编解码 并行计算
【创新未发表!】基于BKA算法优化-BP、HO算法优化-BP、CP算法优化-BP、GOOSE算法优化-BP、NRBO算法优化-BP神经网络回归预测比较研究(Matlab代码)
【创新未发表!】基于BKA算法优化-BP、HO算法优化-BP、CP算法优化-BP、GOOSE算法优化-BP、NRBO算法优化-BP神经网络回归预测比较研究(Matlab代码)
101 0
|
1月前
|
机器学习/深度学习 数据采集 运维
改进的遗传算法优化的BP神经网络用于电厂数据的异常检测和故障诊断
改进的遗传算法优化的BP神经网络用于电厂数据的异常检测和故障诊断

热门文章

最新文章