反悔贪心 & 模拟费用流
参考资料来源 cyt
前言
很多找到一种可行的方案，匹配（选择）某些东西，使价值最优化的问题可以建出费用流模型。
但是直接跑费用流的复杂度是不对的。
我们又想到可以用简单的贪心思路解决这些问题，然而一般的贪心都假掉了。
于是我们考虑模拟费用流的退流操作来做贪心，这就是反悔贪心，其实也是在模拟费用流的各种操作。
反悔堆
用时一定
用时为 \(1\)，使价值最大。
P2949 [USACO09OPEN] Work Scheduling G
按截止时间排序。
接着对于一个工作，若截止时间内还有空，则直接选。
否则我们用一个堆，堆里面放选了的工作，按价值从小到大。
把价值最小的找到，看是否比当前工作的价值更劣，是则用当前工作将它替换。
价值一定
价值为 \(1\)，使工作最多。
还是按截止时间排序。
还是用堆，把用时最长的找到，看用当前工作替换是否更优。
练习
显然先按照 \(x_i\) 排序。
相当于枚举一个走到的位置 \(x_i\)，然后在这个位置之前的机房选要最多个使 $x_i+\sum k\le m $。
注意到 \(x_i\) 选的机房会继承 \(x_{i-1}\) 的。
则每次先把 \(i\) 选了，让 \(sum\) 加 \(f_i\)。
看 \(sum+x_i\) 是否不超过 \(m\)。
否则，拿个堆，一直把最大的 \(f\) 退掉。
注意是一直退掉，而不是用 \(f_i\) 与堆顶做比较，这是因为堆中存的是走到 \(x_{i-1}\) 这个位置的答案，而不是走到 \(x_i\) 的答案。
若最后 \(sum+x_i\) 不超过 \(m\)，则此时选的个数即为走到 \(x_i\) 的最大答案。
对所有可行的答案取最大值即可。
反悔自动机
堆 反悔自动机
CF865D（简易老鼠进洞模型）
考虑在卖出股票时同时结算买和卖。
每一天都买，我们把它插入堆里，插入堆无代价。
每天再看能否卖，若把堆顶现在卖出有收益，则卖出。
但有问题：
我们用当前 \(p_i\) 的价格卖出堆顶的 \(x\) 元买进的股票，收益是 \(p_i-x\)。
但有可能后面有 \(j>i\) 使得 \(p_j-x\) 更优，然而 \(x\) 这个股票已经卖掉了。
解决方案就是，我们用 \(p_i\) 卖掉 \(x\) 的股票时，往堆里再插入一个 \(p_i\)，注意这里的 \(p_i\) 和每天买进的股票不同。
这样若后面有 \(p_j\) 更优，则 \(p_j\) 就会匹配上 \(p_i\)，此时对答案的贡献和即为
\[(x-p_i)+(p_i-p_j)=x-p_j \]就变成了用 \(p_j\) 匹配 \(x\)，自动变成了最优方案。
双向链表+堆 反悔自动机
贪心思路：每次选最大的价值，选 \(k\) 次。
然而选了 \(i\) 后 \(i-1\) 和 \(i+1\) 就不能选了，此时可能会出现选 \(i-1\) 和 \(i+1\) 更优的情况。
发现这种情况只能是 \(i-1\) 和 \(i+1\) 同时选，这样才会比 \(i\) 大。
于是考虑选了堆顶 \(a_i\) 后，把 \(i-1,i,i+1\) 这三个点缩成一个价值为 \(a_{i-1}+a_{i+1}-a_i\) 的点，将它插入堆里。
这样下次选到这个点，就相当于选 \(i-1,i+1\)，同时把原来选的 \(i\) 退掉，代价和为
\[a_i+(a_{i-1}+a_{i+1}-a_i)=a_{i-1}+a_{i+1} \]拿一个双向链表维护当前的前驱和后继即可。
老鼠进洞模型
有 \(n\) 个老鼠，\(m\) 个洞，老鼠有坐标 \(x_i\)，洞有坐标 \(y_i\)，每只老鼠都要进洞。
第 \(i\) 个洞每进一只老鼠花费 \(w_i\) ，最多进 \(c_i\) 只老鼠。
老鼠可以左右移动，花费移动距离的代价。
要求最小化花费。
两个堆 基础模型
考虑洞没有权值，容量 \(c_i\) 都为 \(1\) 时应该怎么做。
先把老鼠和洞放在一起按坐标排序。
为了去掉绝对值的影响，我们把洞匹配老鼠和老鼠匹配洞分开考虑（即让右边匹配左边）。
设 \(i\) 老鼠匹配洞 \(j\)，若 \(i<j\)，则贡献为 \(y_j+(-x_i)\)，反之为 \(x_i+(-y_j)\)。
用反悔贪心的思路，维护一个洞堆和一个老鼠堆，从左往右扫一遍。
如果当前扫到一个老鼠
那么取出洞堆的堆顶让它和这个洞匹配（初始时负无穷处有足够多个洞），设堆顶为 \(v\)，对答案的贡献为 \(x_i+v\)。
为了让右边没扫到的洞使这个老鼠能反悔，让它匹配右边一个新的洞。
那么如果它要匹配右边一个新的洞 \(j\)，那么代价的增量为 \((y_j-x_i)-(x_i+v)=y_j+(-2x_i-v)\)，于是往老鼠堆插入 \(-2x_i-v\)。
如果扫到一个洞
考虑有没有老鼠要反悔来这个洞，从老鼠堆中取出堆顶 \(u\)，若 \(y_i+u<0\) 则更优，让老鼠反悔，加上贡献。
若这个洞原本应当让后面一个老鼠 \(j\) 占，于是让这个洞反悔，往洞堆中插入 \(-2y_i-u\)。
贡献和即 \((y_i+u)+(x_j+(-2y_i-u))=x_j-y_i\)，是正确的。
若没有老鼠能反悔来这个洞，则直接插入 \(-y_i\)。
就像这样（\(A\) 为老鼠，\(B\) 为洞）：
\[B_1\leftarrow A_1\\ \downarrow\\ B_1,A_1\leftarrow B_2\\ \downarrow\\ B_1\leftarrow A_1,B_2\leftarrow A_2 \]初始时 \(A_1\) 匹配 \(B_1\)。
然后 \(A_1\) 反悔，让 \(B_2\) 匹配 \(A_1\)。
后来 \(A_2\) 才应该匹配 \(B_2\)，于是 \(A_1\) 又重新匹配 \(B_1\)。
当然在权值上没有谁匹配谁的关系，我们只需使最后的权值和正确即可。
洞有权值
如果在基础模型的基础上，洞有权值 \(w\) 该怎么做。
区别在于一个老鼠可能会匹配较远的洞。
老鼠匹配洞时有堆最优化，无影响。
而当洞匹配老鼠就有影响了。
首先是贡献为 \(y_i+w_i+u\)。
考虑到我们让洞 \(i\) 匹配老鼠 \(j\) 时，后面可能还有洞 \(k\) 与老鼠 \(j\) 匹配更优。
所以，设 \(u\) 为老鼠 \(j\) 在堆中的权值，则我们用 \(k\) 再匹配 \(j\) 的增量为，\((y_k+w_k+u)-(y_i+w_i+u)=(y_k+w_k)+(-y_i-w_i)\)，所以用 \(i\) 匹配完 \(j\) 后，要往老鼠堆中插入 \(-y_i-w_i\)，让洞 \(k\) 与这个虚拟老鼠匹配。
由于新增的 \(w\) 的影响，扫到一个洞后，有反悔时插入到洞堆的权值就变成了 \(-2y_i-u+w\)，无反悔时插入的权值变为 \(-y_i+w_i\)。
这时你可能会有疑问：
如果洞 \(i\) 在洞堆和老鼠堆插入的两个权值都从堆顶取出了怎么办。
那它应该要长成这样：
\[B_1\leftarrow A_1\\ \downarrow\\ B_1,A_1\leftarrow B_2\\ \downarrow\\ B_1,A_1,B_2,B_3(A_1\leftarrow B_3)\\ \downarrow\\ B_1,A_1,B_2,B_3,A_2(A_1\leftarrow B_3,B_2\leftarrow A_2) \]其中 \(B_2\) 就是被取出两次的洞，它开始匹配 \(A_1\)，后来 \(B_3\) 替换了它，取了一次老鼠堆顶。
然后 \(A_2\) 以为 \(B_2\) 还连着 \(A_1\)，取了一次洞堆顶，它以为它替换掉了 \(B_2\) 连着的 \(A_1\)，然而 \(B_2\) 实际并没有连着 \(A_1\)，那么 \(A_2\) 连 \(B_2\) 时加的权值就不对了。
我们观察一下， 发现这种情况时不可能出现的，因为对于 \(i<j<k<l\)，其中 \(i,l\) 为老鼠，\(j,k\) 为洞，\(i\) 连 \(k\) 并且 \(j\) 连 \(l\) 一定不优，因为 \(i\) 连 \(j\) 并且 \(k\) 连 \(l\) 比这更优。
那么对于上面的例子，最后一行会变成 \(B_1,A_1\leftarrow B_2,B_3\leftarrow A_2\) 或 \(B_1,A_1,B_2,B_3,A_2(B_1\leftarrow A_2,A_1\leftarrow B_3)\)。
所以我们不用担心取两次的情况。