【UER

【UER #8】雪灾与外卖 模拟费用流板子题。 首先可以建立一个简单费用流模型。把点按坐标排序后，不难发现，最终匹配方案不交叉。 那么可以考虑将两类点排序，对费用流的过程进行模拟。模拟的难点在于退流。 考虑一个$x$点。先把它向左边没用匹配的$y$中最优秀的匹配。它的贡献是$x_i+v_j$，其中$v_j$是$y_j$的贡献。 如果在之后将$x_i$现在的匹配退流，那么代价是$-2x_i-v_j$。 考虑一个$y$点。先不管$c$，把一个点拆成$c$个点考虑。让$y$尝试匹配之前的一个$x$。那么贡献是$y_i+w_i+v_j$，其中$v$是之前的代价。 在$y$点退流之后，有一些$x$的匹配改变了。但是明显这些$x$还可以继续改变。此次改变的代价变成了$-y_i-w_i$。 实际上这一过程就是维护两个堆，分别表示两类点，然后做贪心的匹配。时间复杂度$O((n+\sum c)log(n+\sum c))$。 这个是不太过得去的，考虑优化，去掉拆点。可以发现，瓶颈在于每次$y$退流后push的新$x$。发现$c$次push的代价都一样。合并起来，退完后一次性push进去就行了。 复杂度愉快的变成了$O((n+m)log(n+m))$