【洛谷 P5908】猫猫和企鹅 题解(无向图+邻接表+深度优先搜索)

2024-02-01 22:04

本文主要是介绍【洛谷 P5908】猫猫和企鹅 题解(无向图+邻接表+深度优先搜索),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

猫猫和企鹅

题目描述

王国里有 n n n 个居住区,它们之间有 n − 1 n-1 n1 条道路相连,并且保证从每个居住区出发都可以到达任何一个居住区,并且每条道路的长度都为 1 1 1

1 1 1 号居住区外,每个居住区住着一个小企鹅,有一天一只猫猫从 1 1 1 号居住区出发,想要去拜访一些小企鹅。可是猫猫非常的懒,它只愿意去距离它在 d d d 以内的小企鹅们。

猫猫非常的懒,因此希望你告诉他,他可以拜访多少只小企鹅。

输入格式

第一行两个整数 n , d n, d n,d,意义如题所述。

第二行开始,共 n − 1 n - 1 n1 行,每行两个整数 u , v u, v u,v,表示居民区 u u u v v v 之间存在道路。

输出格式

一行一个整数,表示猫猫可以拜访多少只小企鹅。

样例 #1

样例输入 #1

5 1
1 2
1 3
2 4
3 5

样例输出 #1

2

提示

对于 100 % 100\% 100% 的数据,满足 1 ≤ n , d ≤ 1 0 5 1 \le n ,d \le 10^5 1n,d105,保证所有居民区从 1 1 1 开始标号。


思路

首先,定义全局变量。N 是节点的最大数量,cnt 是已访问节点的计数器,vis 是一个布尔数组,用于标记节点是否已被访问,g 是一个向量数组,用于存储图的邻接表表示。

dfs 函数是深度优先搜索的实现。它接受两个参数,一个是当前节点 x,另一个是剩余的探索深度 d。如果当前节点已被访问,或者剩余深度小于0,函数就会返回。否则,函数会标记当前节点为已访问,并增加已访问节点的计数。然后,只要剩余深度不为0,函数就会遍历当前节点的所有邻居节点,并对每一个邻居节点递归调用 dfs 函数,同时将剩余深度减1。

main 函数首先读取节点数量 n 和探索深度 d。然后,读取 n-1 对边的信息,并在邻接表 g 中添加这些边。接着,从节点1开始进行深度优先搜索。最后,输出已访问节点的数量减1(不含初始节点)。


AC代码

#include <cstring>
#include <iostream>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e5 + 7;int cnt;
bool vis[N];
vector<int> g[N];void dfs(int x, int d) {// cout << x << endl;if (vis[x] || d < 0) {return;}vis[x] = 1;cnt++;if (!d) {return;}for (const int i : g[x]) {dfs(i, d - 1);}
}int main() {int n, d;cnt = 0;memset(vis, 0, sizeof(vis));cin >> n >> d;for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, d);cout << --cnt << endl;return 0;
}

这篇关于【洛谷 P5908】猫猫和企鹅 题解(无向图+邻接表+深度优先搜索)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/668611

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

poj 2914 无向图的最小割

题意: 求无向图的最小割。 解析: 点击打开链接 代码: #pragma comment(linker, "/STACK:1677721600")#include <map>#include <set>#include <cmath>#include <queue>#include <stack>#include <vector>#include <cstd

基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(五):Blender锥桶建模

前言 本系列教程旨在使用UE5配置一个具备激光雷达+深度摄像机的仿真小车,并使用通过跨平台的方式进行ROS2和UE5仿真的通讯,达到小车自主导航的目的。本教程默认有ROS2导航及其gazebo仿真相关方面基础,Nav2相关的学习教程可以参考本人的其他博客Nav2代价地图实现和原理–Nav2源码解读之CostMap2D(上)-CSDN博客往期教程: 第一期:基于UE5和ROS2的激光雷达+深度RG

韦季李输入法_输入法和鼠标的深度融合

在数字化输入的新纪元,传统键盘输入方式正悄然进化。以往,面对实体键盘,我们常需目光游离于屏幕与键盘之间,以确认指尖下的精准位置。而屏幕键盘虽直观可见,却常因占据屏幕空间,迫使我们在操作与视野间做出妥协,频繁调整布局以兼顾输入与界面浏览。 幸而,韦季李输入法的横空出世,彻底颠覆了这一现状。它不仅对输入界面进行了革命性的重构,更巧妙地将鼠标这一传统外设融入其中,开创了一种前所未有的交互体验。 想象

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close