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

注意 匹配 和 增广 的区别。

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

先在左边加一个 $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)$。

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