求助，有关时间复杂度

@Daniel_yuan 2020-07-11 18:01 回复

似乎在本题中，形成的偏序关系最多有 $n\times m$ 个（差不多是这个数量级）。那么在整体二分的过程中，用网络流求最大权闭合子图的时候，每一层的总点数都是 $n$，边数最大是 $n\times m$ 的，而一共有 $\log v$ 层，感觉一般的网络流跑起来可能会比较吃力……

我在写本题的时候用的 Dinic（加上了当前弧优化），某个测试点需要在网络流上跑差不多 4s，请问各位神犇是我写丑了还是有什么优化啊……

卡常卡了很久了，一直没有什么进展，故向各位神犇求助。

感激不尽！！！

@cosmicAC 2020-07-11 18:20 回复 举报

众所周知，Dinic跑不满，并且我写的普通的Dinic最慢的点也只要128ms。你是不是使用了memset整个数组等等细节，让复杂度退化了？

@cosmicAC 2020-07-11 18:29 回复 举报

我知道原因了，请把Dinic的Dfs加上这么一行剪枝：

if(d){
    e[i].val -= d;e[i ^ 1].val += d;
    res -= d;sum += d;
    if(!res) break;
}

@Daniel_yuan 2020-07-11 18:38 回复 举报

@cosmicAC 太感谢您了！！！看样子以后写 Dinic 要注意了。

@No268435  2020-07-11 18:58 回复 举报

@Daniel_yuan Orz

@弦巻こころ 2020-07-11 19:01 回复 举报

@Daniel_yuan orz

@LuV_Studio 2020-07-11 19:16 回复 举报

$log n$好香