题目描述
体育场突然着火了,现场需要紧急疏散,但是过道真的是太窄了,同时只能容许一个人通过。
现在知道了体育场的所有座位分布,座位分布图是一棵树,已知每个座位上都做了一个人,安全出口在树的根部,也就是1号结点的位置上。
其他结点上的人每秒都能向树根部前进一个结点,但是除了安全出口以外,没有任何一个结点能够同时容纳两个及以上的人。
这就需要一种策略来使得人群尽快疏散。
请问在采取最优策略的情况下,体育场最快可以在多长时间内完成疏散。
-
输入格式
第一行包含整数n,表示树的结点数量。
接下来n-1行,每行包含两个整数x和y,表示x和y结点之间存在一条边。 -
输出格式
输出一个正整数表示最短疏散时间。 -
数据范围
1≤n≤105,
1≤y≤x≤n
方法:树的遍历,dfs
- 数据范围:N = 10^5, 树状数组
- 时间复杂度:O(?)
- 思路:求根结点子树的最大个数
1. dfs: yxc老师的详细解法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int head[N], e[M], ne[M], idx; // 建立无向边,节点用到的数目*2
// 用邻接表储存树M
void add(int a, int b)
{
e[idx] = b; //新建一个点,储存b,idx表示用过点的个数
ne[idx] = head[a]; // 将新建的点插入成为头节点
head[a] = idx ++ ; // 更新 idx
}
// 返回以u为根节点的树的大小
int dfs(int u, int father)
{
int res = 1; //记录当前点
//遍历当前节点产生的树
for (int i = head[u]; i != -1; i = ne[i])
{
int son = e[i]; //遍历的点为son
if (son != father) res += dfs(son, u); //如果搜索的点不是父节点,那么向下迭代
}
return res;
}
int main()
{
int n;
int a, b;
cin >> n;
memset(head, -1, sizeof head);
for (int i = 0; i < n - 1; i ++ )
{
cin >> a >> b;
add(a, b), add(b, a);
}
//求根节点的每个子树的个数的最大值
// dfs参数:1.当前节点(从当前节点开始搜索) 2.父节点(确保搜索的时候不会反向搜索)
int res = 0;
for (int i = head[1]; i != -1; i = ne[i]) res = max(res, dfs(e[i], 1)); //1是父节点
cout << res << endl;
return 0;
}
2. dfs遍历树的模板写法,基于上一个的一点改进
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int h[N], e[M], ne[M], idx;
bool st[N];
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
// dfs 返回包含当前节点的子树个数和
int dfs(int u)
{
int res = 1; //记录当前节点
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
res += dfs(j);
st[j] = true;
}
}
return res;
}
int main()
{
int n;
cin >> n;
int a, b;
memset(h, -1, sizeof h);
for (int i = 0; i <n - 1; i ++ )
{
cin >> a >> b;
add(a, b), add(b, a);
}
//求根节点所有子树的最大个数, 即为最长时间
int res = 0;
//从根节点开始遍历它相邻的点(即子树的根节点), 不妨设根节点为1
st[1] = true;
for (int i = h[1]; ~i; i = ne[i]) res = max(res, dfs(e[i]));
cout << res << endl;
return 0;
}
3. bfs
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int head[N], e[M], ne[M], idx; // 建立无向边,节点用到的数目*2
int q[N]; // 开一个队列
bool st[N];// 判断数组,表示某个点有没有搜过
// 用邻接表储存树M
void add(int a, int b)
{
e[idx] = b; //新建一个点,储存b,idx表示用过点的个数
ne[idx] = head[a]; // 将新建的点插入成为头节点
head[a] = idx ++ ; // 更新 idx
}
// 返回以u为根节点的树的大小
int bfs(int u)
{
int hh = 0, tt = 0; // 初始化队头和队尾
q[0] = u; //u 加到队列中去
st[u] = true; //表示u点已经搜过
// bfs 模板
while (hh <= tt) //当队列存在时
{
int t = q[hh ++ ]; // 取出队头,并把队头下标加一
for (int i = head[t]; i != -1; i = ne[i]) //遍历队头的每一条边
{
int j = e[i];
if (!st[j]) //如果当前边练的点未被遍历过
{
q[ ++ tt] = j; //把这个点加入到队尾
st[j] = true; //并标记这个点,这是为了防止遍历过的点又遍历一遍
//因为有的时候1的点连接2,3,4;而2的点又连接了3;这样做可以保证
//每个点只遍历一次
}
}
}
return tt + 1; //+1 是因为要加上根节点
}
int main()
{
int n;
int a, b;
cin >> n;
memset(head, -1, sizeof head);
for (int i = 0; i < n - 1; i ++ )
{
cin >> a >> b;
add(a, b), add(b, a);
}
//求根节点的每个子树的个数的最大值
int res = 0;
st[1] = true;
for (int i = head[1]; i != -1; i = ne[i]) res = max(res, bfs(e[i]));
cout << res << endl;
return 0;
}