关于本题复杂度以及题解错误
查看原帖
关于本题复杂度以及题解错误
331947
hegm楼主2024/12/23 21:27

本题由于需要对于每一个节点二分求解答案,并且无法使用整体二分进行优化,因此复杂度理论是 nmlogV+dinicnm\log V+\text{dinic} ,先忽略掉后者。

亲测 VV 的极限取值范围(擦边 AC\text{\color{Green}AC})需要在 0100\sim 10 范围二分且精度为 10610^{-6},因此 logV=log10723\log V= \log 10^7\approx 23。所以前半部分理论复杂度是 700×100000×231.6×109700\times 100000\times 23\approx 1.6\times 10^9

复杂度极其炸裂的同时却能通过本题,然而许多题解认为整体二分是可以优化本题复杂度的,实则不行。(如果您认为整体二分可以优化本题复杂度,希望您可以解释一二)

建议管理撤掉部分错误认为整体二分可以优化复杂度的题解。

也求问本题是否存在理论复杂度更小的做法,

2024/12/23 21:27
加载中...