一棵 n 个节点, 采用堆式存储的完全二叉树. ci 为节点 i 最多能容纳的鸟的数量. m 只鸟, 第 i 只鸟的初始位置为 pi. 移动一只鸟的代价为树上的距离. 对于 k=1,2,...,m, 求将前 k 只鸟安排妥当 (节点上鸟的数目不超过其最大容纳量) 的最小代价. (n,m ≤ 3*10^5) 让我先写一个暴力费用流......
然后就走上了不归路......
尝试了以下4种组合: (保留树的结构, 建成二分图) x (在上一次的残量网络上跑, 每次清空). 要不然就是出现负圈, 要不然就是超级慢, 呜呜呜......
初始没有负圈的图, 如果第一次没有按最短路增广, 也有可能产生负圈.
右边一位大爷表示自己的图没有负圈, 左边一位神犇小哥表示没给一些边建反向弧, 这样就能跑出结果啦......Orz
在上一次的残量网络上加入一些新的边, 再按最短路增广是正确的. 至于为什么正确, 我也不知道......感受一下?
手动模拟费用流. 新加入一只鸟, 就从它的初始位置开始, 找一条最短路增广. 也就是, 找一个容量 > 0, 且距离最近的节点. 如果走向和边上的流向相同, 或边上的流为 0, 费用为 +1; 否则, 费用为 -1.
维护 down[x] 表示子树 x 中容量 > 0 的点与 x 的最近距离. 由于是完全二叉树, 高度