之前写了一个 感性理解 uer8 雪灾与外卖，但是太感性了，所以再写个理性的！！！

先假设你会费用流建图了。从左往右加点维护最小费用最大流。在左边加上无穷个 $w=\infty$ 的餐馆以保证总是一个送餐员的完美匹配。

我们提到流量时，指的总是链上的边。

先考虑 $c=1$。

Observation 1

如果一条边流量为 $0$，那么它两侧的情况分别是单独考虑两侧时的最优解。

Corollary 1

如果一条边在两个不同时刻流量为 $0$，那么这两个时刻它左侧的情况必然相同。

我们让一个点和它左边的边编号相同。

考虑找到最右的流量变为 $0$ 的边，那么它和它右侧的边流量不同，也就是说此处必然有一组匹配。以加入送餐员 $i$ 为例，那么此处必有一个餐馆 $j$。

于是根据上面的结论，这次增广的效果就是把边 $j$ 左侧恢复加入餐馆 $j$ 之前的情况，并从送餐员 $i$ 增广到餐馆 $j$。

Observation 2

由于 $c=1$，流量是连续变化的。（$c>1$ 时，后面的各种结论也类似地成立，但是直接这样看比较简洁，并且 $c>1$ 就可以看成加了一堆 $c=1$ 的，中间边权是 $0$ 嘛）

最右的流量变为 $0$ 的边右侧不会有流量和它同向的边，否则它就不是最右的。

Theorem

我们可能做的事情只有以下几种:

• 加入一个餐馆，不做操作/走一个不经过反悔边的负环。

• 加入一个送餐员，匹配一个未匹配的餐馆。

• 加入一个餐馆，撤销进行了操作4且未被撤销的送餐员中最后加入的那个的操作，并匹配这个送餐员。

• 加入一个送餐员，撤销进行了操作3且未被撤销的餐馆中最后加入的那个的操作，并匹配这个餐馆。

Proof

对时间归纳。先考虑加入送餐员 $i$ 的情况。如果没有边流量变为 $0$，就是进行了一次操作2。

如果有边 $j$ 流量变为 $0$，我们要证明这就是进行了一次操作4。

Observation 3

如果一个之前的餐馆进行了操作3且未被撤销，那么它左侧那条边流量一定是向右的。

Proof

显然刚进行完这个操作时它是向右的。操作2不会改变这条边，操作1/3不会让这条边向右的流量减小。操作4会撤销最后的操作3，不可能让这条边的流量减到 $0$。

所以餐馆 $j$ 一定是"进行了操作3且未被撤销的餐馆中最后加入的那个"。

另一方面，加入餐馆 $j$ 之前的任何操作，和之后的操作2都不经过边 $j$；操作3的匹配部分有可能经过边 $j$，但是它们都被撤销了；操作4的匹配部分不可能经过边 $j$，因为它只可能匹配餐馆 $j$ 之后的餐馆；操作1有可能经过边 $j$，但是如果有这样的操作1，边 $j$ 的流量必然 $>1$，所以没有。

所以所有经过边 $j$ 的操作只剩下加入餐馆 $j$ 这个操作了。撤销加入餐馆 $j$ 时的操作，就把边 $j$ 左侧恢复了。根据前面的结论，这就是这次增广的效果。

然后考虑加入餐馆 $j$。如果没有边流量变为 $0$，就是进行了一次操作1。如果有边 $i$ 流量变为 $0$，要证明就是进行了一次操作3。如法炮制。

Observation 3'

如果一个之前的送餐员进行了操作4且未被撤销，那么它左侧那条边流量一定是向左的。

Proof

显然刚进行完这个操作时它是向左的。操作1不会改变这条边（因为限制了没走反悔边），操作2/4不会让这条边向左的流量减小。操作3会撤销最后的操作4，不可能让这条边的流量减到 $0$。

所以送餐员 $i$ 一定是"进行了操作4且未被撤销的送餐员中最后加入的那个"。

另一方面，加入送餐员 $i$ 之前的任何操作，和之后的操作1都不经过边 $i$（因为限制了没走反悔边）；操作4的匹配部分有可能经过边 $i$，但是它们都被撤销了；操作3的匹配部分不可能经过边 $i$，因为它只可能匹配送餐员 $i$ 之后的送餐员；操作2有可能经过边 $i$，但是如果有这样的操作1，边 $i$ 的流量必然 $>1$，所以没有。

所以所有经过边 $i$ 的操作只剩下加入送餐员 $i$ 这个操作了。撤销加入送餐员 $i$ 时的操作，就把边 $i$ 左侧恢复了。根据前面的结论，这就是这次消负环的效果。

我们要维护这四种操作。使用两个堆分别维护加入餐馆时可能的负环和加入送餐员时可能的增广路的情况。

• 加入一个送餐员。我们在增广路堆中找到堆顶 $v$，给答案加上 $x+v$，并往负环堆中加入 $-(x+v)-x$（提供操作3的机会）。

• 加入一个餐馆。我们在负环堆中找到堆顶 $v$，如果 $v+y+w\geq 0$ 则没有负环，往增广路堆中加入 $-y+w$（提供操作2的机会）；否则给答案加上 $v+y+w$，并往增广路堆中加入 $-(v+y+w)-y+w$（提供操作4的机会），往负环堆中加入 $-(y+w)$（提供操作1的机会）。

但是这里我们把可能不是最后加入的也扔进堆里了，这还对吗？注意到不是最后一个的话，这么算出来的代价只会更大，因为它之后的操作又生成了若干反悔边（它们可能被撤销，但是刚加入它时就有的那些不可能被撤销），而反悔这些边减少的代价并没有被更新。而最后一个本来就是代价最小的，现在肯定还是代价最小的，所以没有问题。

至于 $c>1$ 怎么做，前人之述备矣（