在残量网络跑 SCC, 考虑边 $ (x, y) $ 或者点 $ x, y$

可行边: 要求 $ (x,y) $ 是匹配边或 $ (x,y) $是非匹配边,但 $ x $ 和 $ y $ 处在同一个 SCC 中。

必经边: 要求 $ (x,y) $ 是匹配边且 $ x $ 和 $ y $ 不在同一 SCC 中。

可行点: $ x $ 的出边至少有一条是可行边。

非必经点: 从 S 出发只走 cap = 1 的边能到达 $ x $ , 或者从 T 出发只走 cap = 0 的边能到达 $ y $ 。

可行点/必经点 不知道有没有更简单做法。

分类: 文章

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注