uer8 雪灾与外卖 题解

Querainy · 2023-04-08 19:58:17 · 个人记录

劲爆题。uoj 差评榜 rk3！感觉现有的题解不是很能理解，于是我尝试理解一下并写在这里给大家过目。可能在扯淡。

注意 匹配 和 增广 的区别。

假设你已经会了费用流建图。我们把链横着放，餐馆放在上面，送餐员放在下面。

先在左边加一个 c,w=\infty 的餐馆保证每个送餐员都能匹配。先考虑 c=1 怎么做。

加入一个送餐员的时候，可能的增广路就是从他走到前面的一个餐馆，而如果选择最短增广路，就不会有负环。加入一个餐馆的时候，没有可能的增广路，负环是替换掉之前的一个餐馆，选择最小的负环就不会产生新的负环。为了方便，以下直接用增广路指加入送餐员时产生的增广路，负环指加入餐馆时产生的负环。

问题是增广可能会进行大量的反悔。

但是画一画可以注意到一个牛逼性质。加入一个送餐员 i 的时候，如果他的增广路经过了反悔边，设 j 是右数第一条反悔边的右端点，那么这次增广的影响恰好相当于撤销加入餐馆 j 时走的负环，并从 i 增广到 j。

在这个图中，我们的结论体现为，粉色增广路的左半边必然和蓝色负环的左半边重合。

为什么这是正确的？考虑如果 j 左边没有任何变化，它当然是正确的。由于增广之后 j 左边那条边必然没有流量（注意 c=1），j 左右是独立的，所以 j 左边必然就是加入 j 之前的最优解。撤销加入 j 时增广的负环，就得到了 j 左边的最优解。

那么问题就是说明前面确实没有什么变化。因为 i 增广的时候 j 到 i 这一段是没有反悔边的，归纳一下，j 到 i 之间发生的事情就是一些餐馆走了一个负环，一些送餐员直接做了匹配，一些送餐员撤销了最近的负环并做了匹配（根据归纳假设必然是撤销最近的负环）。那么相当于走过的负环形成了一个栈，没有走负环的餐馆形成了一个堆，加入餐馆时如果走了负环会 push 进栈，否则会 push 进堆，而送餐员选择栈顶和堆顶中更优的来 pop。在 j 加入之后栈顶是 j 走的负环，在 i 加入时栈顶又是 j 走的负环，中间的负环都被加入又撤销了，所以这个结论看起来就很对。

这直接给出一个做法，但是看起来跟官方题解做法不太一样，因为官方题解是把栈顶左边向左匹配的餐馆的反悔也扔进堆里了。为了说明官方题解的正确性，注意到不在栈顶的餐馆算的代价只会更大，因为栈中在它上面的餐馆又生成了若干反悔边，而反悔这些边减少的代价并没有被更新。

加入餐馆的时候走负环的性质是类似的。所以可以用两个堆分别维护最优的增广路和负环，复杂度 O(n\log n)。

具体地。

• 加入一个送餐员。我们在增广路堆中找到堆顶 v，给答案加上 x+v，并往负环堆中加入 -(x+v)-x（提供一个走了反悔边的负环）。

• 加入一个餐馆。我们在负环堆中找到堆顶 v，如果 v+y+w\geq 0 则没有负环，往增广路堆中加入 -y+w（提供一个没有走反悔边的增广路）；否则给答案加上 v+y+w，并往增广路堆中加入 -(v+y+w)-y+w（提供一个走了反悔边的增广路），往负环堆中加入 -(y+w)（提供一个没有走反悔边的负环）。

对于 c 不一定 =1 的情况，这体现在餐馆会走很多次负环。我们把相同的数合并成一个，也就是额外记一个出现次数，那么负环堆每次只会多 O(1) 个元素，并且增广路堆如果加入了 k 个元素，说明负环堆至少少了 k-1 个元素，所以就有均摊了，复杂度还是 O(n\log n)。

我感觉这个题可能做了什么双向链大一统之类的事情，但是我不知道。