关于 Tarjan 的疑问
  • 板块学术版
  • 楼主_Weslie_
  • 当前回复11
  • 已保存回复11
  • 发布时间2024/10/24 07:15
  • 上次更新2024/10/24 12:23:21
查看原帖
关于 Tarjan 的疑问
511959
_Weslie_楼主2024/10/24 07:15

rt,在我做 P1073 [NOIP2009 提高组] 最优贸易 时,发现求从 11nn 的路径中答案时,直接将 11 塞进队列里跑 dp。

但是如果有以下情况:

这样把 11 塞进队列里后,就无法把 33 的所有入边删掉,因此会导致 WA。

所以是因为这道题有特殊性质还是这种情况可能发生且数据没有构造?

如果是一般的 Tarjan 缩点,是否会出现这种情况?

2024/10/24 07:15
加载中...