【FLOYD+并查集】蓝桥杯算法提高 Degrees of Separation

embedded/2025/3/18 18:38:34/

目录

题目详情:

问题描述:

输入说明:

输出说明:

测试用例:

输入:

输出:

题解:

问题分析:

问题1:

问题2:

问题3:

问题4:

题解代码:

Code详细解释:

1. 全局变量与数据结构

2. 并查集操作

3. 初始化函数 init()

4. 节点映射与边处理

5.连通性检测

6.Floyd算法

7.最大分离度计算


题目详情:

 

问题描述:

        在我们联系日益紧密的世界里,人们推测每个人和其他人的分离度不超过六(六度分离)。在这个问题里,你需要写一个程序来找出人们的关系网络中最大的分离度。
  对于任意两个人,他们的分离度是联系两个人需要经过的最小的关系数。对于一个关系网络,最大的分离度是网络中任意两人的分离度的最大值。如果一个网络中有两个人没有通过关系链连接起来,这个网络是不连通的。
  

输入说明:

        输入包含多组描述关系网络的数据,对于每组数据,第一行有两个数P,表示网络中人的数目,和R,关系的对数。接下来一行是R个关系。每个关系用两个字符串表示,代表网络中有关系的两个人的名字。每个名字是不同的,并且中间没有空格。因为一个人可能和多个人有联系,一个名字可能在一组数据中出现多次。
  最后以一行两个0表示结束。

      2<=P<=50,R>=1

输出说明:

        对于每个网络,输出网络中最大的分离度。如果这个网络是不连通的,输出DISCONNECTED。每一个网络输出后再输出一个回车。按照样例输出中的格式输出。

测试用例:

输入:

4 4
Ashok Kiyoshi Ursala Chun Ursala Kiyoshi Kiyoshi Chun
4 2
Ashok Chun Ursala Kiyoshi
6 5
Bubba Cooter Ashok Kiyoshi Ursala Chun Ursala Kiyoshi Kiyoshi Chun
0 0

输出:

Network 1: 2

Network 2: DISCONNECTED

Network 3: DISCONNECTED
 

题解:

问题分析:

问题描述的比较抽象,直接用图来理解。一个关系网络就是一个图,两个人之间的分离度就是两个人之间路径的长度 这是一个不带权图 或者理解为权值等于1也行。题目要求的就是求一个图中 任意两个人的最短路径的最大值,前提是这个图是连通图。如果不是连通图,就输出DISCONNECTED。

我们要解决三个问题:

问题1:

如何判断是否是连通图 我们用并查集实现 

参考我的文章:并查集的学习

问题2:

求两个人之间的最短路径 也就是分离度 用FLOYD算法实现 然后遍历一遍DIS数组找最大值即可

参考我的文章:FLOYD算法

问题3:

一对关系是两个人名 不知道有几对关系的情况 用字符串读取全部人名 然后按空格分割 一次提取两个人名 用字符串流stringstream实现

参考我的文章用getline和stringstream读取一个字符串并按照空格分割

问题4:

输入的是人名,但是数组下标是数字。所以我们用map映射,构建一个map<string,int>.把一个名字映射到一个数字。因为map不会有重复元素。所以每出现一个新名字就在map中创建一对pair加入。就用不一样的数字代表名字。


 

题解代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<set>
#include<sstream>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
int dis[55][55];//两点间距离
int fa[55];//并查集 模板
int finds(int a){int aa=a;//保存一下查找的点 也就是路径的底部if(a!=fa[a]){fa[a]=finds(fa[a]);//找到了根节点}while(aa!=fa[a]){//向上更新整条路径int temp=fa[aa];//先存储路径的下一个点fa[aa]=fa[a];//路径压缩一个aa=temp;//再压缩下一个点}return fa[a];
}void unions(int x,int y){int fx=finds(x);int fy=finds(y);if(fx!=fy){fa[fx]=fy;}
}
void init(){//初始化fa数组 dis数组 便于多次for(int i=0;i<55;++i){fa[i]=i;for (int j=0;j<55;++j){if(i==j){dis[i][j]=0;//自己到自己距离为0}else{dis[i][j]=INF;}}}}
int main(){int x,y;int cas=0;//输出第几个网络while(cin>>x>>y){cin.get();//读取一个空格if(!x&&!y){break;}init();//初始化string temp;getline(cin,temp);stringstream str(temp);string word1,word2;map<string,int>m;int num=0;while(str>>word1>>word2){if(m.find(word1)==m.end()){m.insert(make_pair(word1,num++));}if(m.find(word2)==m.end()){m.insert(make_pair(word2,num++));}int a=m[word1];int b=m[word2];unions(a,b);//并查集dis[a][b]=1;dis[b][a]=1;}//判断是否连通if(num<x){//点少于总点数 肯定不联通printf("Network %d: DISCONNECTED\n", ++cas);cout<<endl;continue;}int sum=0;//用并查集看是否属于同一个集合for(int i=0;i<x;++i){if(sum>1){break;}if(fa[i]==i){sum++;}}if(sum!=1){printf("Network %d: DISCONNECTED\n", ++cas);cout<<endl;continue;}//floyd 计算最短路径for(int k=0;k<x;++k){//中转点for(int i=0;i<x;++i){//每一对邻接点for(int j=0;j<x;++j){dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}}}int maxdis=-INF;for(int i=0;i<x;++i){//每一对邻接点for(int j=0;j<x;++j){maxdis=max(dis[i][j],maxdis);}}printf("Network %d: %d\n", ++cas, maxdis);cout<<endl;}return 0;
}

Code详细解释:

1. 全局变量与数据结构
  • dis数组:初始化为INF(无穷大),表示初始不可达;对角线dis[i][i]设为0(自己到自己距离为0)。
  • fa数组:并查集的父节点数组,用于快速判断连通性。
2. 并查集操作

  • 路径压缩:确保查找操作的时间复杂度接近O(1)。
  • 合并操作:将两个节点所在的集合合并,用于后续连通性判断。
3. 初始化函数 init()

  • 作用:每次测试用例开始前,重置并查集和距离矩阵。
4. 节点映射与边处理
  • 使用map<string, int>将节点名转换为连续的整数ID(如0, 1, 2,...)。
  • 对于每对节点,设置dis[a][b] = dis[b][a] = 1,表示直接相连。
5.连通性检测
  • 条件1num < x:若实际节点数少于输入的x,说明输入数据不完整,网络不连通。
  • 条件2:通过并查集统计根节点数量。若根节点数sum != 1,说明存在多个连通分量。
6.Floyd算法

  • 原理:三重循环遍历所有可能的中间节点k,更新所有点对的最短路径。
  • 正确性:确保所有路径的最小值被计算。
7.最大分离度计算
  • 遍历所有点对,排除i == j的情况,取最大值maxdis

http://www.ppmy.cn/embedded/173648.html

相关文章

插入排序算法的SIMD优化

一 概述 插入排序是稳定的原地排序算法,核心思想是逐步构建有序序列。对于未排序部分的每个元素,在已排序序列中从后向前扫描,找到合适位置插入。 二 SIMD 1 SIMD定义 通过单条指令同时处理多个数据元素(如同时计算4个float的加法)。 2 指令集支持 SSE 系列:SSE/SS…

K近邻分类算法适合做什么又不适合做什么

K近邻&#xff08;K-Nearest Neighbors, KNN&#xff09;是一种简单且直观的分类算法&#xff0c;广泛应用于各种机器学习任务。然而&#xff0c;它也有其局限性。以下是KNN算法适合和不适合的场景&#xff1a; ​1.适合的场景&#xff1a;​ ​小规模数据集&#xff1a; KNN适…

MacOS 15.3.1 安装 GPG 提示Error: unknown or unsupported macOS version: :dunno

目录 1. 问题锁定 2. 更新 Homebrew 3. 切换到新的 Homebrew 源 4. 安装 GPG 5. 检查 macOS 版本兼容性 6. 使用 MacPorts 或其他包管理器 7. 创建密钥&#xff08;生成 GPG 签名&#xff09; 往期推荐 1. 问题锁定 通常是因为你的 Homebrew 版本较旧&#xff0c;或者你…

SWPU 2021 新生赛

babyunser phar反序列化 利用文件查看器直接读到三个文件 read.php <?php include(class.php); $anew aa(); ?> error_reporting(0); $filename$_POST[file]; if(!isset($filename)){die(); } $filenew zz($filename); $contents$file->getFile(); ?> <b…

MCU的应用场景:从智能家居到工业控制

MCU的应用场景非常广泛&#xff0c;主要包括以下几个方面&#xff1a; 1. 智能家居 智能照明&#xff1a;通过MCU控制LED灯的亮度和颜色。 智能安防&#xff1a;在安防系统中&#xff0c;MCU用于控制传感器和报警器。 2. 工业控制 PLC&#xff08;可编程逻辑控制器&…

动作捕捉手套如何让虚拟现实人机交互 “触手可及”?

在虚拟与现实逐渐交融的当下&#xff0c;动作捕捉技术正以前所未有的速度革新着多个领域。 动作捕捉技术&#xff0c;简称“动捕”&#xff0c;已经从早期的影视特效制作&#xff0c;逐步拓展到游戏开发、虚拟现实、机器人控制等多个领域。 而mHandPrO数据手套作为这一领域的…

【AI学习从零至壹】Pytorch神经⽹络

Pytorch神经⽹络 神经网络简介神经元激活函数 神经网络神经⽹络的⼯作过程前向传播(forward) 反向传播(backward)训练神经⽹络 Pytorch搭建并训练神经⽹络神经⽹络构建和训练过程数据预处理构建模型优化器&提取训练数据训练样本 神经网络简介 神经元 在深度学习中&#x…

AI驱动的视频字幕提取与翻译工具

青梧字幕是一款基于Whisper技术的AI字幕提取工具&#xff0c;专为视频制作者、翻译人员和自媒体创作者设计。它通过先进的语音识别算法&#xff0c;能够自动从视频文件中提取字幕内容&#xff0c;并支持多种语言和字幕格式&#xff0c;极大地简化了字幕制作流程。 目前暂支持 …