本题由于需要对于每一个节点二分求解答案,并且无法使用整体二分进行优化,因此复杂度理论是 nmlogV+dinic ,先忽略掉后者。
亲测 V 的极限取值范围(擦边 AC)需要在 0∼10 范围二分且精度为 10−6,因此 logV=log107≈23。所以前半部分理论复杂度是 700×100000×23≈1.6×109。
复杂度极其炸裂的同时却能通过本题,然而许多题解认为整体二分是可以优化本题复杂度的,实则不行。(如果您认为整体二分可以优化本题复杂度,希望您可以解释一二)
建议管理撤掉部分错误认为整体二分可以优化复杂度的题解。
也求问本题是否存在理论复杂度更小的做法,