求助,有关时间复杂度
查看原帖
求助,有关时间复杂度
71955
Daniel_yuan楼主2020/7/11 18:01

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

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

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

感激不尽!!!

2020/7/11 18:01
加载中...