反悔贪心（模拟费用流）_LCA

反悔贪心（模拟费用流）

模拟费用流的重点是维护流一步、以及维护负环。

只要能维护这两个，就无需维护退流，并且进行任意形式的修改（即给定一个残量网络）都能保证正确性。

思考的时候最好先从最优化形式想到费用流，再从费用流模型系统地思考这两个问题，以及如果不维护负环，能不能证明正确性。

noip模拟赛11.20 T4

两个数组 $a,b$ 长度都是 $n$，A 和 B 博弈（B 是机器人），B 每次会机械地选 $\max b_i$，并把答案减去 $b_i$，A 可以选一个 $a_i$（可以不是最大的）并把答案加上 $a_i$，A 先手且希望答案最大。

单点修改 $a$，每次求答案。

$n,q\le 5\times10^5$。

按照 $b$ 从大到小排序，设 $sum_i$ 表示 $[1,i]$ 中 A 选了几个，则只需满足 $sum_i\le \lceil i/2\rceil$。

贪心地选，我们至多能选出 $\lceil n/2\rceil$ 个，且不论怎么设定优先级，我们总是会选出 $\lceil n/2\rceil$ 个数，构造方法是如果没有选满，那么 $n$ 位置是松的，那最后一个没选的位置一定能选，这个影响是一个后缀减，不会造成不合法。

那这个题有优先级吗，还真有，强定初始所有人都被 B 选了，那么选一个数的贡献就是 $a+b$。

既然数量固定，那么更改后如果我们要改变当前的状态，例如我们要选这个点，那就一定替换掉另外一个点。

那会不会发生两个点替换掉两个点的情况？这等价于我们要对 负环的长度 分析。

假设我们某次修改后 $(a,b)$ 替换为了 $(c,d)$，我们首先将合法性拆分成独立的部分：若 $a\to c$ 和 $b\to d$ 方向不同且有交，那么 $a\to d$ 和 $b\to c$ 一定不会方向不同且有交。

也就是说要么方向相同（都是区间减或都是区间加），要么无交，这两种情况合法性都是独立的，即我们可以自由拆分为先 $a\to c$ 再 $b\to d$。

由于选一个数的贡献是 $a+b$，我们又只改了一个数，那么必定有一个是不优的，如果两个都优，那么修改之前就应该执行其中一项。

将两个点换成为多个点的证法是类似的，只需要两边排序然后匹配就满足要么同向要么无交。

百度之星2024决赛 T111

建出模型后，我们用 $k^2$ 个 pq 来维护颜色间的替换关系，一个一个加入，发现新图上的最短路只需要考虑 $k$ 个点之间的最短路，那直接爆搜最短路或者跑 spfa 都可以通过。

老鼠进洞 CF797F Mice and Holes

P4698 [CEOI2011] Hotel

[AGC018C] Coins