蓝桥杯每日真题 - 第20天

题目:(机房)

题目描述(13届 C&C+G题)

 

解题思路:

这道题目可以看作在一个无向图中查找两点之间的最短路径。题目中的 n 台电脑和 n−1 根网线形成了一棵树,树是一个特殊的无向图,因此我们可以利用 广度优先搜索(BFS) 来求解最短路径问题。

  • 建图

    • 通过输入的 n−1 对电脑连接关系构建邻接表表示的无向图。

  • 最短路径搜索

    • 利用 BFS,从起点开始逐层扩展,找到终点时输出步数。

    • 由于树的性质,BFS的第一条找到的路径一定是最短路径。

  • 多个查询的处理

    • 每次查询直接用 BFS 求解从起点到终点的最短路径。

 

代码实现(C语言):

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int road(int start,int end,int dex,int num,int bef,int n);
int map[10000][10000];
int dey[10000];
int main()
{    int n,m;scanf("%d",&n);scanf("%d",&m);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j){map[i][j]=1;}else{map[i][j]=0;}}dey[i]=-1;}for(int i=1;i<=n-1;i++){int a;int b;scanf("%d",&a);scanf("%d",&b);map[a][b]=1;map[b][a]=1;}int q[m+1][2];for(int i=1;i<=m;i++){scanf("%d",&q[i][0]);scanf("%d",&q[i][1]);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dey[i]=dey[i]+map[i][j];}}for(int i=1;i<=m;i++){printf("%d\n",road(q[i][0],q[i][1],q[i][0],0,-1,n));}return 0;
}int road(int start,int end,int dex,int num,int bef,int n)
{//printf("%d to %d have %d\n",bef,dex,num);if(dex==end){return num+dey[dex];}else{int new_num=num+dey[dex];int lin=-100;int e=0;for(int i=1;i<=n;i++){if(i!=dex && map[i][dex]==1 && i!=bef){lin=fmax(lin,road(start,end,i,new_num,dex,n));e=e+1;}}if(e==0){return -100;}else{return lin;}}
}

得到运行结果:

代码分析: 

  • 初始化部分

    • 通过输入节点数n和边数m,创建一个邻接矩阵来表示图,初始化每个节点的度数为-1。

    • 将图的边输入,并更新邻接矩阵。

  • 查询输入部分

    • 输入多个查询,每个查询要求计算从一个节点到另一个节点的路径代价。

  • 计算每个节点的度数

    • 遍历邻接矩阵,计算每个节点的度数,并将其存储在一个数组中。

  • 计算路径代价的递归函数

    • 使用深度优先搜索(DFS)递归遍历路径,如果当前节点是终点,则返回路径代价;否则,继续递归遍历与当前节点相邻的未访问节点。

    • 每到一个节点,路径代价会累加该节点的度数。

  • 输出查询结果

    • 对每个查询,调用递归函数计算路径代价,并输出结果。

难度分析

⭐️⭐️⭐️⭐️⭐️

总结

  • 图的表示:采用邻接矩阵和度数数组表示图。

  • 深度优先搜索(DFS):使用递归方法遍历路径并计算路径代价。

  • 路径代价计算:路径代价由路径上经过的所有节点的度数之和来确定。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/476206.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

iOS应用网络安全之HTTPS

移动互联网开发中iOS应用的网络安全问题往往被大部分开发者忽略, iOS9和OS X 10.11开始Apple也默认提高了安全配置和要求. 本文以iOS平台App开发中对后台数据接口的安全通信进行解析和加固方法的分析. 1. HTTPS/SSL的基本原理 安全套接字层 (Secure Socket Layer, SSL) 是用来…

项目虚拟机配置测试环境

在企业中&#xff0c;有专门的服务器部署开发环境&#xff0c;测试环境等等 直接在虚拟机中打开虚拟机就可以 dps查看容器

初始ArkUI

一. 什么是ArkUI ArkUI基于方舟UI框架为应用的UI开发提供了完整的基础设施&#xff0c;UI语法更加简洁&#xff0c;丰富的UI功能&#xff08;组件、布局、动画以及交互事件&#xff09;&#xff0c;以及实现界面预览工具等&#xff0c;可以支持开发者进行可视化界面开发。 &a…

【PCIE常见面试问题-1】

PCIE常见面试问题-1 1 PCIE概述1.1 PCI为何发展开PCIE&#xff1f;1.2 什么是Root Complex(RC)1.3 什么是EP&#xff1f;1.4 什么是Swith1.5 PCIE协议如何组织通信的&#xff1f;1.6 简要介绍一下PCIE的分层结构&#xff0c;为什么需要分层&#xff1f;1.7 PCIE的事务类型有哪些…

用pyspark把kafka主题数据经过etl导入另一个主题中的有关报错

首先看一下我们的示例代码 import os from pyspark.sql import SparkSession import pyspark.sql.functions as F """ ------------------------------------------Description : TODO&#xff1a;SourceFile : etl_stream_kafkaAuthor : zxxDate : 2024/11/…

什么是反向 DNS 查找以及它的作用是什么?

反向DNS查询&#xff08;rDNS&#xff09;是一种技术&#xff0c;用于确定与某个IP地址对应的域名。当我们对一个IP地址进行反向DNS查询时&#xff0c;实际上是向域名系统&#xff08;DNS&#xff09;的特殊部分请求信息&#xff0c;这部分被称为PTR记录。PTR记录会返回与这个I…

HarmonyOS鸿蒙系统上File文件常用操作

HarmonyOS鸿蒙系统上&#xff0c;file文件常用操作记录 1.创建文件 createFile(fileName: string, content: string): string {// 获取应用文件路径let context getContext(this) as common.UIAbilityContext;let filesDirPath context.filesDir / fileName;// 新建并打开…

音视频pts/dts

现在的视频流有两个非常重要的时间戳&#xff0c;pts和dts&#xff0c;其中pts是显示的时候用&#xff0c;dts在解码的时候用。 pts很好理解&#xff0c;按照pts的顺序以及duration不间断的display就可以了。 dts在解码的时候用&#xff0c;那么这句话怎么理解&#xff0c;解…

输出比较简介

输出比较简介 主要是用来输出PWM波形&#xff0c;这个波形是驱动电机的&#xff08;智能车和机器人等&#xff09;必要条件 OC&#xff08;Output Compare&#xff09;输出比较&#xff0c;还有IC&#xff0c;全称是Input Capture&#xff0c;意为输入捕获&#xff0c;还有CC…

揭秘AIGC下的数字时代:交互设计的隐秘力量与未来革命

在当今数字化时代&#xff0c;交互设计已经成为我们日常生活中不可或缺的一部分。它不仅仅是关于产品或服务的界面设计&#xff0c;更是关于如何通过这些界面与人进行有效的沟通和互动。本文将探讨交互设计的深层含义、面临的挑战以及其对未来科技发展的影响。 文章来源&#x…

使用node-addon-api实现从c到nodejs模块全流程

目录 1 前言 2 安装nodejs 3 安装开发工具链 3.1 安装node-gyp 3.2 安装编译工具链&#xff08;C/C 编译器&#xff09; 4 初始化 Node.js 项目 4.1 创建项目目录 4.2 初始化 package.json 4.3 安装必要的库 5 编写代码 5.1 创建项目结构 5.2 编写动态库代码 5.3 编…

Python3.11.9+selenium,获取图片验证码以及输入验证码数字

Python3.11.9+selenium,获取图片验证码以及输入验证码数字 1、遇到问题:登录或修改密码需要验证码 2、解决办法: 2.1、安装ddddocr pip install ddddocr 2.2、解析验证码函数 import ddddocr def get_capcha_text():#获取验证码图片ele_pic = driver.find_element(By.XPAT…

测试工程师如何在面试中脱颖而出

目录 1.平时工作中是怎么去测的&#xff1f; 2.B/S架构和C/S架构区别 3.B/S架构的系统从哪些点去测&#xff1f; 4.你为什么能够做测试这一行&#xff1f;&#xff08;根据个人情况分析理解&#xff09; 5.你认为测试的目的是什么&#xff1f; 6.软件测试的流程&#xff…

css水平居中+垂直居中

display:“flex”,position: “absolute”,top:“50%”,left:“50%”,transform: ‘translate(-50%, -50%)’

Linux 服务器使用指南:从入门到登录

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; &#x1f6a9;博主致力于用通俗易懂且不失专业性的文字&#xff0c;讲解计算机领域那些看似枯燥的知识点&#x1f6a9; 目录 一…

99.【C语言】数据结构之二叉树的基本知识

目录 1.树的定义 树是递归定义的 一些细碎的概念 2.树的判断法则 树结点结构的定义 自然想到的定义方法 左孩子右兄弟定义 3.树的应用:文件系统 4.树的特殊形式:二叉树 5.特殊的两类二叉树 满二叉树 完全二叉树 完全二叉树和满二叉树之间的关系 高度为h的完全二叉…

Bug:引入Feign后触发了2次、4次ContextRefreshedEvent

Bug&#xff1a;引入Feign后发现监控onApplication中ContextRefreshedEvent事件触发了2次或者4次。 【原理】在Spring的文档注释中提示到&#xff1a; Event raised when an {code ApplicationContext} gets initialized or refreshed.即当 ApplicationContext 进行初始化或者刷…

Ubuntu20.04从零安装IsaacSim/IsaacLab

Ubuntu20.04从零安装IsaacSim/IsaacLab 电脑硬件配置&#xff1a;安装Isaac sim方案一&#xff1a;pip安装方案二&#xff1a;预构建二进制文件安装1、安装ominiverse2、在ominiverse中安装isaac sim&#xff0c;下载最新的4.2版本 安装Isaac Lab1、IsaacLab环境克隆2、创建con…

低速接口项目之串口Uart开发(二)——FIFO实现串口数据的收发回环测试

本节目录 一、设计思路 二、loop环回模块 三、仿真模块 四、仿真验证 五、上板验证 六、往期文章链接本节内容 一、设计思路 串口数据的收发回环测试&#xff0c;最简单的硬件测试是把Tx和Rx连接在一起&#xff0c;然后上位机进行发送和接收测试&#xff0c;但是需要考虑到串…

算法编程题-排序

算法编程题-排序 比较型排序算法冒泡排序选择排序插入排序希尔排序堆排序快速排序归并排序 非比较型排序算法计数排序基数排序 本文将对七中经典比较型排序算法进行介绍&#xff0c;并且给出golang语言的实现&#xff0c;还包括基数排序、计数排序等非比较型的算法的介绍和实现…