模拟费用流_LCA

模拟费用流

重要性质

模拟费用流的流量通常表现为选点的个数，在构造时要对着这个构造。

在图不变的情况下：

• 增广一次（多 $1$ 的流量），与源汇相连的边不会发生退流。
• 增广一次，增广路不会经过一个点两次，否则意味着上次的结果中有负环。

若我们（通常在匹配问题中）新增了一个点/一条边：

• 若本来不能增广，现在能增广，则无需处理负环（最小费用最大流），如果是最小费用流仍有负环。
• 其他情况需要考虑负环。

问题类

• 静态问题，通常还会限定个数（限定流量），图不变。

此时满足图不变的性质，无论如何都不存在负环。

• 第 $i$ 个时刻新增了一个人，即我们要在原图上加点加边。

例如 P9168 [省选联考 2023] 人员调度，P6122 [NEERC2016] Mole Tunnels。

此时我们需要考虑负环的性质，若保证可以增广的话，加一条边不用担心负环，例如后者。

人员调度就属于可能无法增广的，此时需要维护负环，即所谓的“替换”。

增广路、负环的长度需要依据“增广路不会经过一个点两次”来确定。

有的时候，问题比较简单，我们有可能把静态问题中的点依次加入，当作动态问题来做。

模拟最短路

最基础的模拟费用流，通常是某侧点数很少的二分图匹配问题。

百度之星2024决赛T11

有 $n$ 个元素 $k$ 个集合，第 $i$ 个元素放到第 $j$ 个集合的价值是 $a_{i,j}$，第 $j$ 个集合最多装 $c_j$ 个元素，对每个元素前缀求最大价值。

$n\le10^5,k\le 10$。

建出图后发现是二分图匹配，且集合那一侧只有 $k$ 个点。

考虑维护最短路的过程，最短路显然不会重复经过同一个点，所以仅仅考虑集合那一侧，最多也就倒腾 $k$ 次。

我们维护 $k^2$ 个堆，$q_{i,j}$ 表示将 $i$ 中的元素替换到 $j$ 中最大获得的价值，从前到后每加入一个元素我们就对这 $k$ 个点跑一遍 $\rm spfa$，复杂度是 $n\cdot(\text{spfa})\cdot\log n$。

CF730I 是本题的弱化版，$k=2$。

老鼠进洞模型 - 单向链/双向链/树 上匹配

单向链：P4694 [PA2013] Raper

你需要生产 $k$ 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。

你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间，每天可以先送一张光盘到 A 工厂（或者不送），然后再送一张已经在 A 工厂加工过的光盘到 B 工厂（或者不送），每家工厂一天只能对一张光盘进行操作，同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。

求生产出 $k$ 张光盘的最小花费。

保证 $1 \leqslant k \leqslant n \leqslant 5 \times 10^5,$ $1 \leqslant a_i, b_i \leqslant 10^9$。

构造其费用流模型，发现这是一条单向链（$S\to$ 链 $a_i$，链 $b_i\to T$），每个点匹配后面的洞。

考虑直接对费用流进行模拟。

正着匹配显然是维护最小的 $i\le j,a_i+b_j$，这个显然可以用线段树维护。

但我们也可以走反向边倒着匹配，我们直接维护 $h_i$ 表示 $(i,i+1)$ 之间反向边的流量。

还要支持对 $h$ 区间加，乍一看不好维护，观察核心性质：一个区间要么 $h$ 的最小值被屏蔽其他存活，要么全部存活。

直接用线段树维护即可单 $\log$。

好写的双 $\log$ 写法：带权二分 + 从左往右反悔贪心，将模型视作特殊二分图（每个点连一个后缀）上的最大权匹配。

每次加入 $a_i,b_i$，由于加入 $a_i$ 时没有能与 $a_i$ 匹配的洞，所以只需扔进堆里留待之后匹配，加入 $b_i$ 时要么不匹配，要么替换一个别的匹配中的 $b_i$，要么选一个 $a_i$ 进行匹配。

若一个 $b_i$ 被替换下来了，之后加入的 $a$ 都是更靠后的，它一定没用了。

在流模型上的体现：$b_i$ 之间替换就是负环，手玩发现不会出现 $a$ 替换 $b$ 替换 $c$ 的情况，因为这种情况等价于 $a$ 替换 $c$。

一般图匹配

NFLS2023.NOV 某题 & QOJ1173

给定 $n$ 个区间，无交的区间两两连一条边，求一般图最大匹配。

$n\le4\times 10^5$。

先考虑贪心匹配，按照左端点升序，维护一个右端点越小越优先的堆，有能匹配的区间就匹配，否则就把当前区间扔进堆里。

我们发现这样可能不优，因为可能出现两个匹配的区间都作为左区间匹配两个右区间的情况。

我们考虑反悔贪心，在扫到第一个右区间的时候把答案中的右区间“换”出来当左区间。

我们发现这需要答案中右区间的右端点小于当前区间的右端点，否则不如不换。

所以我们维护所有答案右区间的右端点的最小值即可。

林毅大法

大力出奇迹，在序列维上的问题，只要我们发现它是凸的/有费用流做法，直接不对图进行分析，而是列出简单的，能被我们维护的所有调整方案，并维护它们，绝大多数情况下这是对的。

「NOI2019」序列

2025 – 炼石计划 elite【省选集训】冬令营 – 模拟赛 #4 括号序列

杂