关于为什么要累加最大流

P2754 [CTSC1999] 家园 / 星际转移问题

这是 Dinic+在残量网络上逐层加点 做法的特性,二分答案之类的每次都建一张新图跑的做法,是不累加的。 考虑建完 day-1 层的图之后跑了一遍 Dinic,然后再把第 day 层的点加上去(直接在残量网络上加)。 此时通过前 day-1 层的月亮通向 T 的增广路都已经全部增广完了,故这一遍 Dinic 不会计算它们的贡献。 它们的贡献恰好是之前的最大流之和,于是,这种做法是累加最大流的。
by wei_xin @ 2022-12-08 15:58:09


|