首页 > 试题广场 >

紧急疏散

[编程题]紧急疏散
  • 热度指数:2273 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
体育场突然着火了,现场需要紧急疏散,但是过道真的是太窄了,同时只能容许一个人通过。现在知道了体育场的所有座位分布,座位分布图是一棵树,已知每个座位上都坐了一个人,安全出口在树的根部,也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点,但是除了安全出口以外,没有任何一个结点可以同时容纳两个及以上的人,这就需要一种策略,来使得人群尽快疏散,问在采取最优策略的情况下,体育场最快可以在多长时间内疏散完成。

数据范围:

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


输出描述:
输出仅包含一个正整数,表示所需要的最短时间
示例1

输入

6
2 1
3 2
4 3
5 2
6 1

输出

4
这测试用例专门用来恶心python的吧,我是真服了。。。
思路就是找1的子节点为根的子树中,含有节点数的最大值
然后如果用dfs递归来找每个子树含有节点数量 ,只能过80%,报错 RecursionError: maximum recursion depth exceeded in comparison
老老实实用bfs或者dfs写迭代吧,正常来说用一个数组visited = [False]*(n+1)记录已经访问过的节点,这么写也只能通过80%,会提示超时
但是把visited设成一格集合,每次检查节点是否在集合中,这样子就能通过了。。。
from collections import defaultdict
n = int(input())
d = defaultdict(set)
for _ in range(n-1):
    a, b = map(int, input().split())
    d[a].add(b)
    d[b].add(a)
'''
def dfs(x, pre): # 写成递归会报错,只能过80%
    global res # dfs返回x及以下总结点数
    total = 0 # total记录所有子节点的总节点数之和
    for nxt in d[x]: # 对所有子节点递归
        if nxt != pre:
            tmp = dfs(nxt, x)
            total += tmp
            if tmp > res: res = tmp # 题目最后答案为节点1所有子节点中总节点数的最大值
    return 1 + total 
res = 0
dfs(1,-1)
print(res)
'''
res = 0 # 迭代法,输出res为1的所有子节点的树所含节点最大值
for nxt in d[1]:
    visited = set([1,nxt]) # 这里visited如果设置成数组[False]*(n+1),就会超时
    q = [nxt] # dfs
    cnt = 0 # cnt记录每个子节点的树中节点总量
    while q:
        cur = q.pop()
        cnt += 1
        for i in d[cur]:
            if i not in visited: 
                q.append(i)
                visited.add(i)
    if cnt > res: res = cnt
print(res)
发表于 2022-02-15 19:29:02 回复(0)