(Preface)
模拟费用流是一个非常巧妙的算法，余之前也对其进行了许多研究，但一直没有触碰到它的本质：模拟费用流，自然就是在费用流的基础上模拟。
因此呐，这次余找到一道比较好也比较有难度的例题，来进行一次模拟费用流算法的巩固深化复习。
前置知识
[NOI2019] 序列
- 给定两个长度为(n)的整数序列({a_i},{b_i})。
- 要求在两个序列中分别选出恰好(K)个数，其中至少有(L)对数下标相同。
- 求出数的总和的最大值。
- 数据总数(le10)，(sum nle10^6)，(1le Lle Kle nle 2 imes 10^5)，(1le a_i,b_ile10^9)
费用流
考虑暴力费用流，建图如下：
解释：一般的边对应选出一对下标相同的数的情况。由于能任选(k-l)对，因此任选边(p ightarrow p')的流量是(k-l)。
然而直接跑费用流显然是无法通过此题的。
模拟费用流
模拟费用流是对费用流的模拟，接下来的每种情况其实都在费用流的图中有着对应的流法（于括号中给出）。
考虑(p ightarrow p')肯定是最优的边，因此先贪心将其流满。
具体地，对两个序列各自开一个堆，每次选出还未选择过的(a)中最大元素(a_u)和(b)中最大元素(b_v)，将总流量(k)以及(p ightarrow p')的容量减(1)。
（(S ightarrow S' ightarrow u ightarrow p ightarrow p' ightarrow v' ightarrow T)）
然而如果(b_u)或者(a_v)已经被选择过了，那么就可以让它们不流(p ightarrow p')这条任选边，而是从一般的边上走，此时可以将(p ightarrow p')的容量加(1)。
（(S ightarrow S' ightarrow u ightarrow u' ightarrow T)或(S ightarrow S' ightarrow v ightarrow v' ightarrow T)）
流满了(p ightarrow p')，接下来有(3)种选择：
- 选择一对都未选过的(a_x,b_x)。（(S ightarrow S' ightarrow x ightarrow x' ightarrow T)）
- 选择一个最大的(a_u)，以及一个最大的(a_v)已经被选过的(b_v)。相当于将原先与(a_v)通过任选边连接的(b)转送给(a_u)，而(a_v)和(b_v)自己走一般边（但要注意如果(b_u)也已经被选过了，需要将(p ightarrow p')容量加(1)重新执行一开始的操作）。（(S ightarrow S' ightarrow u ightarrow pleftarrow v ightarrow v' ightarrow T)，其中左箭头表示走反向边，即退流操作）
- 选择一个最大的(b_v)，以及一个最大的(b_u)已经被选过的(a_u)。同上。
具体实现也就是开五个堆，分别存储剩余的最大的(a_u)、剩余的最大的(b_v)、最大的(b_u)已经被选过的(a_u)、最大的(a_v)已经被选过的(b_v)、都未选过的(a_x,b_x)。
(Postscript)
至此，终于可以对模拟费用流算法进行一次总结了：
- 模拟费用流的本质，是在费用流的基础上模拟。（
所以不会费用流一切都白搭） - 模拟费用流的核心，是贪心。（
说实话很多模拟费用流题目反而是利用费用流去证明贪心的正确性） - 模拟费用流的实现，通常会用到堆。
- 模拟费用流的题目，大都非常玄学。（
废话）
咳咳，这就是余目前能想到的有关模拟费用流的全部内容啦！