chaoswinder 在 MinecraftMinecraft 的世界里,圈了一块地建成了一个小王国。现在,为了让首都的消息能够及时传到王国每个角落,他在王国各地建立了驿站,而驿站则由 “聪明” 的村民们打理。 村民之间通信的规则是这样的:一共有 nn 个村民,每个村民有一个编号 i(1<=i<=n)i(1<=i<=n) ,编号为 i 的村民可以将消息传递给编号为 2*i,2*i+12∗i,2∗i+1 的村民,总耗时 1 分钟,,一个村民传递给另一个村民叫做一条边,共有 mm 条边 (0<=m<=n-1)(0<=m<=n−1) 每次传达消息时,chaos 会把消息交给编号为 1 的村民,让其帮忙传达。 由于 chaos 与村民相处日久,也变得一样傻乎乎,现在他把村民的数量和村民们之间的通信关系都列了出来...... 请你帮帮他想想,把消息传达给所有村民,最快需要几分钟?(C语言)
时间: 2024-02-17 07:01:41 浏览: 17
这是一个树形结构,可以使用 BFS(广度优先搜索)进行遍历,每经过一个村民,就把它的编号和时间加入队列中,然后再继续遍历它的下一级村民。直到遍历完所有的村民,最后一个到达的村民就是耗时最长的那一个,它的到达时间就是传递消息的最短时间。
以下是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100005
int n, m; // n 个村民,m 条边
int head[MAXN], ver[MAXN], nxt[MAXN], idx = 0; // 邻接表存储图
int depth[MAXN]; // 每个村民的深度
int ans = 0; // 最短时间
void add(int a, int b) {
ver[++idx] = b;
nxt[idx] = head[a];
head[a] = idx;
}
void bfs() {
int q[MAXN], hh = 0, tt = 0;
q[0] = 1; // 从第一个村民开始传递消息
depth[1] = 0;
while (hh <= tt) {
int t = q[hh++];
for (int i = head[t]; i; i = nxt[i]) {
int j = ver[i];
if (depth[j] == 0) { // 如果这个村民还没有被遍历过
depth[j] = depth[t] + 1; // 更新这个村民的深度
q[++tt] = j; // 把这个村民加入队列
}
}
}
for (int i = 1; i <= n; i++) {
ans = ans > depth[i] ? ans : depth[i]; // 找到最长的传递时间
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
bfs();
printf("%d\n", ans);
return 0;
}
```
这个算法的时间复杂度为O(m+n),其中m为边数,n为节点数。