题解的证明都挺扯淡的
查看原帖
题解的证明都挺扯淡的
224443
pp_orange楼主2024/3/7 13:48

对缩点那步正确的证明应该是归纳法说明边双可以赋方向后变成SCC,然后所有边全部反向同样是SCC。由于SCC已经是最强的连通性条件,而且每个边都有正反两种方案了,所以可以缩点。

题解区所说的,边双可以不通过每个边,所以这个边没有方向实际上是伪证,因为并不能说明去掉这个边之后存在解。针对删边的那步证明是可以hack的。

2024/3/7 13:48
加载中...