将人做为节点,构建一个顶点数 V,边数为 E 的无向图。节点之间至少有一个链接。
所有人从 1 到 V 进行编号。
将人分为感染者和非感染者。最初只有编号 n1,n2,…,nx 的 X 人是感染者,他们各自拥有感染时间是 m1,m2,...mx 。 所谓某疾病的感染时间 m,是指从感染该疾病的时刻开始正好 m 时间后病会痊愈。
另外规定最初的感染者是在时刻 0 时感染的。
人们仅在满足以下所有条件时,才会在 T 时刻得病,得病后的感染时间为 P:
相邻是指 A 和 B 之间直接相连。
要求输出 Y 时刻,还在生病的人的数量。
测试输入:
4 4 1 2 //节点数 边数 第 0 秒的感染人数 输出数据的时间点
1 //第几节点被感染
2 //感染持续的时长
1 2 //从这里开始到结束都是节点之间的连接关系
1 3
2 3
2 4
输出:3
1
lxy42 2020-11-03 20:59:55 +08:00
问题描述好像缺少疾病传播时间, 如果假设是 1 个单位时间的话:
可以使用 BFS, 初始队列是所有初始病人节点, 访问深度相当于时刻, 深度每增加 1, 时刻也加 1. |
2
vance123 2020-11-05 03:21:00 +08:00 via Android
生命游戏?
|