V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Wolfsin
V2EX  ›  问与答

问一道关于图的面试题,刷的题不多,写了好久也没写出来

  •  
  •   Wolfsin · 2020-11-03 20:29:48 +08:00 · 774 次点击
    这是一个创建于 1499 天前的主题,其中的信息可能已经有所发展或是发生改变。

    将人做为节点,构建一个顶点数 V,边数为 E 的无向图。节点之间至少有一个链接。

    所有人从 1 到 V 进行编号。

    将人分为感染者和非感染者。最初只有编号 n1,n2,…,nx 的 X 人是感染者,他们各自拥有感染时间是 m1,m2,...mx 。 所谓某疾病的感染时间 m,是指从感染该疾病的时刻开始正好 m 时间后病会痊愈。

    另外规定最初的感染者是在时刻 0 时感染的。

    人们仅在满足以下所有条件时,才会在 T 时刻得病,得病后的感染时间为 P:

    • 在 T 时刻时是非感染者,并从未被感染过。
    • 在 T-1 时刻时,与剩余感染时间 P 的感染者相邻。
    • 如果 T-1 秒时与复数的感染者相邻,那么得病时的感染时间 P 为相邻感染者中剩余感染时间最长。

    相邻是指 A 和 B 之间直接相连。

    要求输出 Y 时刻,还在生病的人的数量。


    测试输入:

    4 4 1 2  //节点数 边数 第 0 秒的感染人数 输出数据的时间点
    1 //第几节点被感染
    2 //感染持续的时长
    1 2 //从这里开始到结束都是节点之间的连接关系
    1 3
    2 3
    2 4
    

    输出:3

    2 条回复    2020-11-05 03:21:00 +08:00
    lxy42
        1
    lxy42  
       2020-11-03 20:59:55 +08:00
    问题描述好像缺少疾病传播时间, 如果假设是 1 个单位时间的话:

    可以使用 BFS, 初始队列是所有初始病人节点, 访问深度相当于时刻, 深度每增加 1, 时刻也加 1.
    vance123
        2
    vance123  
       2020-11-05 03:21:00 +08:00 via Android
    生命游戏?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2713 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 14:36 · PVG 22:36 · LAX 06:36 · JFK 09:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.