现在翻了翻复习 zp 时的小奥讲义,有一道题不知该怎么做。
现在看来,这是一道网络最大流模板,若考试时用 Dinic,时间复杂度 O(v2v^{2}v2e), 图中有 8 个点 10 条边,需要 640 次运算,zp 一题平均两三分钟,请问人脑如何在考场上 AC,用预流推进?那难度是 省选/NOI-,不会做,求助大佬们。