关于此题分层图做法正确性的一些小疑问
查看原帖
关于此题分层图做法正确性的一些小疑问
670826
NianFeng楼主2024/7/22 15:29

这个标题好长。

说正事。在观察分层图做法的时候,我想到一个问题。建新图时,一条边的边权设为了原入点的权值,这让我大为疑惑:为什么不会选重?

个人认为,分层图对于同一点/同一边贡献不重复计的情况是不好处理的,特别是这种反边的情况。思索之下,这道题分层图拥有正确性大抵是因为贝西(贝茜?)会回到出发点。

在题解区做法中,起点没有计贡献。而由于 DAG 的性质,唯一一条逆行的边一定连回起点或者从起点出发,所以分层图做法正好避开了重选现象。(等一下,这好像不对,比如 1->2 2->3 4->3 4->5 5->1。管不了那么多了qwq)

但是,如果终点设为 nn 号点呢?这样一来,分层图做法就会假飞。举个栗子,当图为一条链,稍微手模以下就会发现问题。因此,分层图做法是非常不严谨的。

望有神犇能给予一点解答,感激不尽。

2024/7/22 15:29
加载中...