Push-Relabel/预流推进 可能的WA原因

P3376 【模板】网络最大流

Blithe_C @ 2023-03-19 17:35:34

看了一圈只有另一个贴提到在这用HLPP预流推进的问题,这题我用HLPP一定会在#2、#3、#5、#6 WA(在P4722不会)。调了半天发现造成问题的不是重边和自环,而是进入源点和从汇点出的边。预流推进方法需要把这两种边删掉,不然在源汇点上push会让结果与正确值差几个这样的边的权值。


|