从《老鼠进洞》开始，浅谈模拟费用流

部分内容来自 WC 2018 PPT。另外，我真的是浅谈。

前置知识

在学习一下的内容之前，你需要至少学会费用流相关概念，反悔贪心相关概念和堆。

当然了，你还要有足够学会模拟费用流的 OI 基础，因为本文会略去一部分比较 trivial 的道理。

老鼠进洞（其一）

有 \(n\) 个老鼠 \(n\) 个洞，每只老鼠向左走到任意一个洞里，最小化所有老鼠的移动距离和。

其实直接贪心即可。

另一方面，这个问题等价于有洞的权值 \(y_i\)，老鼠的权值 \(x_i\)，求最小权匹配。这本质上可以费用流，但是如果数据范围很大就不太好办了。因此考虑费用流是怎么跑的。

因为费用流的本质是反悔贪心，所以我们决定从这个角度出发来研究模拟费用流。从左向右依次扫洞和老鼠，不断进行匹配，为了让后边的老鼠可以反悔，我们设 \(f[i][j]\) 为前 \(i\) 个节点中有 \(j\) 个洞匹配了 \(i\) 之后的老鼠的最小权。那么这个 \(dp\) 很好通过栈优化，略去这一部分。

老鼠进洞（其二）

有 \(n\) 个老鼠 \(n\) 个洞，每只老鼠走到任意一个洞里，最小化所有老鼠的移动距离和。

显然，我们可以仿照老鼠进洞（其一）的方法解决。但是这个问题的复杂之处在于存在 \(j<0\) 的情况。在老鼠进洞（其一）中，我们采用了一个栈来优化转移。而在老鼠进洞（其二）中，我们则需要两个栈分别维护 \(j\le0\) 和 \(j>0\) 两种情况。

此称为栈模拟费用流。

当然我们也可以直接进入正题，说一个堆优化反悔贪心的有趣解法。

首先，我们不管三七二十一的一顿乱匹配（也就是不考虑其正确性），然后不断扫描来更新答案。

我们要维护目前尚未匹配的老鼠，目前尚未匹配的洞，所有老鼠反悔操作的代价和所有洞反悔的代价。在我们从左向右扫描所有的洞和老鼠的时候，我们会遇见以下的情况：

• 扫描到了一只老鼠。
• • 此时，我们选取一个目前尚未匹配的洞（如果有的话）并将其匹配，如果没有的话，将其和无穷远点匹配，代表尚未匹配。
• • 然后，我们寻找所有洞反悔操作的代价最小值，如果代价加上收益大于目前这只老鼠的收益，将洞从堆顶取出，将洞和老鼠匹配，把新的代价放在堆中。本质上，这是洞在反悔，因为出现了新的老鼠。
• • 不管如何，我们把这只老鼠匹配到的洞记下来，再记一下它的反悔代价，扔在老鼠的堆里。
• 扫描到了一个洞。
• • 这时，我们选取一个目前尚未匹配的老鼠（如果有的话）并将其匹配。如果没有的话，与无穷远点匹配，代表尚未匹配。
• • 然后，我们寻找所有老鼠反悔代价的最小值，如果代价加上收益大于目前这只老鼠的收益，将老鼠从堆顶取出，将洞和老鼠匹配，把新的代价放在堆中。本质上，这是老鼠在反悔，因为出现了新的洞。
• • 不管如何，我们把这个洞匹配到的老鼠记下来，再记一下它的反悔代价，扔在洞的堆里。

老鼠进洞（其三）

有 \(n\) 个老鼠 \(n\) 个洞，每只老鼠向左走到任意一个洞里，洞有代价。最小化所有老鼠的移动距离和与代价加和的和。

Sol 1：发现了一个凸函数，可以 wqs 二分了

Sol 2：不难发现，其二的费用流方法可以扩展。因为老鼠不可能反悔选择更右侧的洞，所以我们直接去掉老鼠反悔这一环节。另一方面，我们只需要稍稍改一下反悔代价，这个做法可以轻松过掉老鼠进洞（其三）。

老鼠进洞（其四）

有 \(n\) 个老鼠 \(n\) 个洞，每只老鼠走到任意一个洞里，洞有容量。最小化所有老鼠的移动距离。

Sol 1：有一个特别牛的 Lemma 是，如果定向老鼠必须全部向左/向右走，所得到的答案对应洞的权值加和，与原容量取 \(\min\) 之后的结果，其容量必定不小于某组最优解所用掉的对应的洞的容量。容易证明这个东西最后用掉的容量和应该是 \(O(n)\) 的，因此就转化成了老鼠进洞（其二）。

Sol 2：其实就是其二加上了容量。何足为惧？在其二的模拟费用流算法中，多记一个目前的容量，此题也被秒掉了。

嗯就先写到这里。事实上，我认为老鼠进洞（其二）的费用流解法虽然大材小用，但十分实用，是很值得学习的方法。

前面的区域，以后再来探索吧！