求助,有关时间复杂度

回复帖子

@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;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。