首页 > 试题广场 >

寻找牛妹

[编程题]寻找牛妹
  • 热度指数：459 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有n个房间，房间之间有通道相连，一共有n-1个通道，每两个房间之间都可以通过通道互相到达。

牛牛一开始在1号房间。牛妹在某个另外的房间。牛牛想去寻找牛妹，但是他没有地图，所以只能在房间之间乱走。
牛牛每走过一条通道需要花费1金币，每条通道最多只能走两次。
牛牛有一个乱走规则：如果当前牛牛有 没走过的通道 可以走，牛牛就不会去走 走过一次的通道
这个规则可以保证只要钱足够就一定可以找到牛妹。

有m个查询，每次询问如果牛妹在x_i号房间，请问牛牛身上至少要带多少金币才可以保证任何情况下都可以找到牛妹。

示例1

输入

4,1,[1,2,2],[2,3,4],[3]

输出

[4]

说明

花费金币最多的方案是1->2->4->2->3

备注:


第一个参数n代表房间数量
第二个参数m代表查询数量
第三、四个参数vector u,v代表通道，u_i与v_i通过通道相连
第五个参数vector x代表m次查询中牛妹的位置
算法知识视频讲解
开通博客
头像 未来0116
发表于 2021-09-02 11:33:20
一.题目描述NC571寻找牛妹n个结点之间有n-1条边，有一个目标数组X，其中有m个目标结点，从根结点走到每个目标结点Xi，每条边最多可以走两次，问从根结点走到每一个目标节点最多可以经过几条边?二.算法(暴力搜索)首先我们要理解题意，但对于n个节点之间有n-1条边我们可以认为其是一个树，由于其连通性 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Peterliang
发表于 2021-09-10 15:42:42
题意分析 给出一个以1为根的树，然后是m个询问，对于每个询问，需要我们计算从结点1到这个被询问的结点的最大的花费是多少？（题目中说的是至少要带多少金币才可以保证任何情况下都可以找到牛妹，所以应该是一个最大的花费。） 思路分析 首先，我们观察题目，我们发现这个题目是一个多组询问，所以应该是需要先 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-09-26 18:38:26
题目的主要信息： n个房间一共n-1个通道相连，每个房间可互相到达，这就是一棵无向树 牛牛一开始在1号房间，要到另一个房间去找牛妹，这个过程中每条痛道最多只能走两次，且如果当前牛牛有没走过的通道可以走，牛牛就不会去走走过一次的通道 每次走过一条通道花费1金币，一共m个查询，每次查询牛妹在xix_i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-08-16 14:55:00
题目关键信息：n个结点之间有n-1条边，有一个目标结点数组，其中有m个目标结点，从根结点走到每个目标结点，每次可以经过最多多少条边，其中，每条边最多可以走两次方法一：dfs每条边最多可以走两次，因此,从根结点到目标结点的通道只能走一次，目标结点和它的所有孩子结点的通道都不用走，因此，从根结点到目标结 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树
难度：
2条回答 3212浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号