反悔贪心（模拟费用流）

反悔贪心（模拟费用流）

贪心本身是不能反悔的，但如果当前最优解不是全局最优解，我们就需要通过反悔来贴近全局最优解。一般用堆来实现，即堆中维护当前可以用来反悔的决策，然后每次取最优的决策。

其实从更一般的角度，反悔贪心就是建出费用流模型，然后用数据结构来模拟增广的操作。

一些例题：

CF280D k-Maximum Subsequence Sum

思路：求区间选出至多\(k\)个不相交的子段和的最大值

思路：如果\(k=1\)，那么就相当于求最大子段和，可以直接贪心，可是如果拓展到\(k\)更大的情况呢？如果我们每次都直接贪心选取最大子段，这样可能会使已经选过的数不再是最优解，即需要撤销操作，而这道题的撤销就很好处理，这直接取反就可以了，接下来就是线段树的事情了。

P6122 [NEERC2016]Mole Tunnels

题意：有一棵完全二叉树，有\(m\)个人在位置\(p_i\)，每个点有\(c_i\)的容量，对于\(k\in[1,n]\)，求使得前\(k\)个人移动到使得每个点的人数不大于这个点容量的最小总代价。

思路：首先，显然可以简单的建立一个费用流模型，然后考虑来模拟费用流。每假如一个人，我们要做的就是找到一条增广路。设 \(f_i\) 表示一个点子树里距离它最近的 \(c_i>0\) 的位置，然后我们遍历新加的点的所有祖先，求出最小的代价，然后把路径上的正向边流量减1，反向边流量加1。边的流量可以简单的用一个数组维护，我们在经过的时候优先走对方的反向边，这样代价是-1，根据流量正负即可判断。

因为树高是\(O(\log n)\)的，所以复杂度是\(O(n\log n)\)。

P6943 [ICPC2018 WF]Conquer The World

题意：有一棵树，有边权\(c_i\)，每个点有点权\(x_i\)，移动每单位的点权的代价是经过的边的边权和，求总代价和的最小值。

思路：设\(dep_x\)表示\(x\)到根的路径的边权和，那么把一个点权从\(u\)移动到\(v\)的代价是\(dep_u+dep_v-2dep_{lca}\)。我们考虑如果要撤销一次移动的操作，可以操作一次\(u\)的代价改成\(-dep_v+2dep_{lca}\)，就可以代表我们撤销了一次操作。

具体的，我们维护两个堆，分别表示当前子树里有的点权和需要的点权，然后每次选择代价最小的进行操作，然后将\(-dep_v+2dep_{lca}\)加入堆中。从孩子处继承时，可以使用可并堆做到\(O(n\log n)\)。

P3543 [POI2012]WYR-Leveling Ground

题意：给定\(n\)个数，每次可以选择一段区间\(+a,-a,+b,-b\)，问最少操作几次可以把所有数变成0。

思路：首先，如果每个数不是\(\gcd(a,b)\)的倍数肯定无解，否则就有解，因此关键在于最少的操作次数。首先考虑做差分，那么区间加就变成了单点加。我们来看差分序列的某个数\(c_i\)，那么假设\(a,b\)分别用\(x,y\)个，就有\(ax+by=c_i\)，可以用拓展欧几里得求出同解，那么对于单个点，肯定是要让\(|x|+|y|\)最小，而且可以证明让总答案最小的就是\(|x|+|y|\)最小的一对\((x,y)\)。

现在的任务是让\(+-\)配对，而只有\(\sum x_i\ne 0\)时需要调整，只要调整好了，\(\sum\frac{|x|+|y|}{2}\)就是答案。调整时考虑贪心。假设\(\sum x_i>0\)就需要把一个\(x_i\)减小，对应的\(y_i\)增加，如果要保证最优就用堆来维护即可。

April Fools' Problem (hard)

题意：有\(n\)道题，第\(i\)天可以花\(a_i\)准备一道题或者花\(b_i\)打印一道题，每天最多准备一道、打印一道，求最少的准备并打印\(k\)道题的花费。

思路：看到恰好\(k\)道就想到wqs二分，而看起来又很贪心，于是就把两个结合起来。

首先二分一个值\(mid\)表示每次打印的额外花费，然后在每个点有两种决策，准备一道题或者打印前面代价最小的一道题，这个过程可以用堆来维护，于是就可以了。复杂度\(O(n\log n\log V)\)。

5.24联考T1

给定一个序列，要求选出一个子序列，设下标为\(p_1,p_2\cdots p_k\)，那么需要满足\(\forall i\in[1,n],A-i\times X+\sum\limits_{p_j\leqslant i}(a_{p_j}+X)\geqslant 0\)，同时要使\(\sum\limits_{i=1}^m[b_i-b_{i-1}-\sum[b_{i-1}<p_j\leqslant b_i]\geqslant h_i]\)最大。

思路：考虑第一个条件就是把没选的数当做\(-X\)，选了的数当做\(a_i\)，满足前缀和始终不小于\(-A\)，而价值就是每个区间选择的数尽量少。考虑DP。设\(f[i][j]\)表示当前在第\(i\)个区间，当前价值为\(j\)，此时前缀和最大是多少，转移时用反悔贪心来计算当前区间内的贡献即可。

P3620 [APIO/CTSC2007] 数据备份

题意：有 \(n\) 个数，要求选出 \(k\) 个互不相邻的数使得和最大。

思路：很经典的反贪。

贪心的策略就是每次选最大的，但是这样做显然不对，考虑怎么反悔。

我们反悔的操作就是把选了一个点不选，然后选择它相邻的未被选择的两个，于是我们选择一个后把它的权值改成左边的加上右边的然后减掉自己的权值即可。