首页 > 试题广场 >

紧急疏散

[编程题]紧急疏散

热度指数：2273 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

体育场突然着火了，现场需要紧急疏散，但是过道真的是太窄了，同时只能容许一个人通过。现在知道了体育场的所有座位分布，座位分布图是一棵树，已知每个座位上都坐了一个人，安全出口在树的根部，也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点，但是除了安全出口以外，没有任何一个结点可以同时容纳两个及以上的人，这就需要一种策略，来使得人群尽快疏散，问在采取最优策略的情况下，体育场最快可以在多长时间内疏散完成。

数据范围： $1 \le n \le 10^5 \$

输入描述:

第一行包含一个正整数n，即树的结点数量。 接下来有n-1行，每行有两个正整数x，y，表示在x和y结点之间存在一条边。(1<=x，y<=n)

输出描述:

输出仅包含一个正整数，表示所需要的最短时间

示例1

输入

输出

算法知识视频讲解

laglangyue

发表于 2020-06-28 22:20:18

查找子树的结点数量bfs import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { 展开全文

Antrn

发表于 2020-10-31 17:42:51

C++ 版本，这个题目的意思就是除了一号节点可以同时容纳多人之外，其他每个节点和路径上都只能某一时刻有一个人通过。那么我们就可以直接从1号节点的子节点开始计算到达安全出口所需要的步骤数。由于我们可以使用哈希表获得每个节点的子节点，所以选择使用bfs，最后取1号节点所有子节点做为根节点时候其所有子节点展开全文