关于NOI 2019 D1T1的图的形态疑惑
  • 板块学术版
  • 楼主2020kanade
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/6/19 13:32
  • 上次更新2023/10/27 23:00:03
查看原帖
关于NOI 2019 D1T1的图的形态疑惑
456724
2020kanade楼主2022/6/19 13:32

看到讨论和题解里说“因为时间单向流逝所以不可能成环”,但是这边自己想了想:

题目中允许重边存在,那么有可能存在一个点是一个环的一部分,绕这个环走一圈的时间(包括等待)与干等相同(比如不需要等并且边权都适当),同时这个点还有另一条唯一的出边走向终点且整个图只有起点、终点还有这个环,起点、终点与上面提到这个点直接相连。

这个时候再把 AA , BB , CC 开一个合适的值,干等的代价就直接上天了,而绕圈的代价显然线性。

人话:可能存在结点 uu 直接与 11nn 连接且直接走 u>nu->n 需要等待,结点 uu 同时在一个内向环中,通过构造数据使在这个内向环上走一圈的时间与直接在 uu 等待相同且在环上的时间中总等待时间极小或为 00 。此时往环上跑一圈很可能优于直接等待。

求以上想法的正确性......

2022/6/19 13:32
加载中...