关于 缩点+拓扑+分层图最长路 做法
  • 板块学术版
  • 楼主Eleveslaine
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/9/21 09:34
  • 上次更新2023/11/2 18:55:01
查看原帖
关于 缩点+拓扑+分层图最长路 做法
450246
Eleveslaine楼主2023/9/21 09:34

这个做法为什么是对的:P3119,https://www.luogu.com.cn/blog/450246/xia-ji-yi-xia-zuo-fa-post

现在感觉就是,拓扑排序求分层图最长路完全有可能在第二层图经过第一层图已经经过的结点(例如第一层图经过 scc[u]\mathrm{scc}[u] 的出边,第二层图又经过 scc[u]+N\mathrm{scc}[u]+N 的一条出边)。这样答案不会出现问题吗?还是说,可以证明对点 11 的答案没有影响?/kel

2023/9/21 09:34
加载中...