首页 > 试题广场 >

紧急疏散

[编程题]紧急疏散

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

输出

算法知识视频讲解

秋叶原の黑猫

package main

import(
    "bufio"
    "os"
    "strings"
    "strconv"
    "fmt"
)

func main(){
	input:=bufio.NewScanner(os.Stdin)
	input.Scan()
	n,_:=strconv.Atoi(input.Text())

	m:=make([][]int,n+1)
	visited:=make([]bool,n+1)

	for k:=0;k<n-1;k++{
		input.Scan()
		nums:=strings.Split(input.Text()," ")
		var temp [2]int
		for i,j:=range nums{
			num,_:=strconv.Atoi(j)
			temp[i]=num
		}
		m[temp[0]]=append(m[temp[0]],temp[1])
		m[temp[1]]=append(m[temp[1]],temp[0])
	}
	res:=0
	visited[1]=true
	for i:=0;i<len(m[1]);i++{
		visited[m[1][i]]=true
		que:=[]int{m[1][i]}
		temp:=0
		for len(que)!=0{
			temp++
			t:=que[0]
			que=que[1:]
			for j:=0;j<len(m[t]);j++{
				if !visited[m[t][j]]{
					que=append(que, m[t][j])
					visited[m[t][j]]=true
				}
			}
		}
		if temp>res{
			res=temp
		}
	}
	fmt.Println(res)
}

发表于 2022-04-04 11:37:46 回复(0)