模拟费用流小记

# 0. 概论 费用流问题是 OI 中的一个应用广泛的经典模型，可以解决种类繁多的最优化问题，以思路巧妙，变化多端著称。 然而，与良好的普适性相对，费用流常用算法的效率较为低下，只能处理较小的数据范围。 在一些特殊的费用流模型中，可以利用题目的特殊性质，结合数据结构等技巧，设计更高效的费用流算法，称之为“模拟费用流”。 这种思路先将原问题转化为费用流问题，再进一步转化成其他更简化的（数据结构）问题。 其中，费用流模型扮演了关键的桥梁角色，帮助我们规范分析，洞察性质，并施展积累的经验技巧。 - **参考资料** - 陈江伦（laofu） WC2019 讲义 《模拟费用流问题》 # 1. 费用流模型与常用性质 费用流基础知识可见 : [网络流/二分图相关笔记(干货篇)](https://www.luogu.com.cn/blog/command-block/wang-lao-liu-er-fen-tu-xiang-guan-bi-ji-gan-huo-pian-post) 下面也开列一些有用的事实。 为了便于叙述，默认为最小费用流。 - ### 费用流经典算法 - **EK** : 每次寻找最短的增广路进行增广。（ zkw和EK本质相同，只是实现方式不同 ） - **消圈** : 先随意求出一个流，然后不断消去图中的负环。 可以直接模拟上述算法的思路，也可以基于这些算法的正确性，设计类似的规则。 - ### 费用流的凸性 根据 EK 算法，增广路的长度会不断增长，则费用是关于流量的凸函数。 - ### 费用流问题的变形 - **最小费用任意流** : 可用 EK 求解，每次增广最短路，当单次费用为正时停止。 - **负费用最大流** : 可用 EK 求解，每次增广最短路，当总费用非正时停止。 上述做法由凸性易证正确性。 - **增量-最小费用任意流** : 每次在图中增加一些点和边，并求解新的最小费用任意流。 只需考虑所有新的 “源到汇的负路径” 以及 “负环” 的贡献。 也可以看做源和汇之间有容量为无穷的边连接，这样“源到汇的负路径”实际上就是“负环”。 - ### 经典结论 - 在非增量费用流中，源汇边不会退流。 - 增广路不会多次经过同一个点。 # 2. 经典例题 - $\large\color{blue}\bf\Delta$ [P4694 [PA2013]Raper](https://www.luogu.com.cn/problem/P4694) **题意** ： 你需要生产 $k$ 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。 现在有 $n$ 天时间。 每天可以先送一张光盘到 A 工厂（或者不送），然后再送一张已经在 A 工厂加工过的光盘到 B 工厂（或者不送），每家工厂一天只能对一张光盘进行操作，同一张光盘在一天内生产出来是允许的。 每天两工厂加工的费用不尽相同， A 工厂第 $i$ 天的要价为 $a_i$， B 工厂即为 $b_i$。 求生产出 $k$ 张光盘的最小花费。 ------------ - **费用流模型** 从源点向每天的 A 厂连边，容为 $1$ ，费用为 $a_i$。 从每天的 B 厂向汇点连边，容为 $1$ ，费用为 $b_i$。 从第 $i$ 天的 A 厂向 $i\leq j\leq n$ 的第 $j$ 天的 B 厂连边。 限制源的总流量为 $k$。 不难发现，这是一个类似于费用匹配的问题。 ------------ - 解法 A : **WQS二分** + **模拟费用流** 这是市面上流传较广的解法。 费用流告诉我们，这个问题的答案关于 $k$ 有凸性，故可以使用 WQS 二分来优化。 在二分惩罚 $C$ 之后，只需要给全体 $a_i$ 加上 $C$。此时不需要再考虑 $k$ 的约束。 考虑使用 “**增量-最小费用任意流**” 模型。 依次考虑 $a_n...a_1$ ，它们能匹配的 $b$ 的集合依次增大。相当于在图上依次增加点。 考虑新加入的两个点以及相关的边能引出怎样的 “源到汇的路径” 以及 “环” ：  如图 I ，红色边为新加入的边（方向确定），黑色边为旧的边，方向是不确定的（可能由于增广而反向） - 源汇路径 ： 必然经过 S 惟一的红出边，所有 T 的入边都是可选的。这对应选择一个最小的未被匹配的 $b$ 进行匹配。如图 II 。 - 负环 ： 经过讨论，图中可能的新环只有形如图 III,IV 的两种形式。 对于形式 III ，对应以目前的 $a$ 替换掉之前的一个比较大的 $a$。 对于形式 IV ，实际上永远不优。其可以拆分成一条 S→T 和一条 T→S。由于所有 T→S 的权值必定小于 0 （否则当初不会选取），故该方案不如单走一个 S→T。 然而，在有流量限制的原问题中，单走一个 S→T 可能不合法，使得我们的证明失效。这也是为什么我们要用 WQS 二分去掉 $k$ 的限制。 上述合法的两种决策容易用堆维护（注意还需维护匹配个数），故复杂度为 $O(n\log^2n)$。 ------------ - 解法B : **直接模拟费用流** 考虑直接模拟 EK 算法，直接在整张图上增广。 不难发现，增广的过程中，必然不会退掉和源点、汇点直接相连的边，只有中间的边可能被退流。 为了彻底规避对退流的分析，我们可以根据源汇边的状态来判定中间的边是否可能合法。 具体地，将操作 A （增广一条源边）视作左括号，操作 B （增广一条汇边）视作右括号，方案合法当且仅当括号构成合法的括号序列。 由于源汇边不会退流，每次增广都**恰会增加一对括号**，且保持括号序列合法。 于是，我们将原问题转化为了对括号序列的维护。 将 $($ 记为 $+1$ ，而 $)$ 记为 $-1$ ，则合法括号序列的充要条件是 : 前缀和均为正。记 $S_i$ 为括号权值的前缀和。 若增加的括号为 $i:(,\ \ j:)$ ，分两类讨论。 - $i\leq j$ ，即选出 `...(...)...` ，则 $S_{[i,j)}$ 加一。 - $i>j$ ，即选出 `...)...(...` ，则 $S_{[j,i)}$ 减一，这要求操作前区间内所有 $S$ 大于 $0$。 使用线段树维护，对于区间 $[l,r]$，记录下列值 : - $mxl$ : 左括号权值最小值。 - $mxr$ : 右括号权值最小值。 - $mxl2$ : 左括号权值最小值，设位置为 $A_i$ ，还需满足 $[l,i)$ 内的最小值严格大于区间最小值。 - $mxr2$ : 右括号权值最小值，设位置为 $B_i$ ，还需满足 $[i,r]$ 内的最小值严格大于区间最小值。 - $mxs$ : $S$ 的最小值。 - $tg$ : $S$ 的加法标记。 - $ans1$ : $i\leq j$ 时的最佳答案。 - $ans2$ : $i>j$ 时的最佳答案（不考虑是否合法）。 - $ans3$ : $i>j$ 时的最佳答案，还需满足 $[j,i)$ 内的最小值严格大于区间最小值。 具体转移见代码。 由于 $S_{1\sim n}$ 必定 $\geq 0$ ，且 $S_n$ 恒为 $0$ ，故每次取出节点 $[1,n]$ 的 $ans1,ans3$ 中的较优解。 复杂度 $O(n+k\log n)$。 此做法能分别求出 $k=1\sim n$ 时的答案。 [评测记录](https://www.luogu.com.cn/record/48904400) ------------ - [CF865D Buy Low Sell High](https://www.luogu.com.cn/problem/CF865D) （**老鼠进洞其一**） **题意** ： 已知接下来 $n$ 天的股票价格 $c_i$，每天你可以买进一股股票，卖出一股股票，或者什么也不做。 假设你拥有无限本金，求 $n$ 天之后能得到的最大利润。 ------------ - $\small\blacksquare$ **费用流模型** 这也是一个费用匹配问题。 从源点向每天连边，容为 $1$ ，费用为 $-c_i$。 从每天向汇点连边，容为 $1$ ，费用为 $c_i$。 每天向第二天连边，容为 $+\infty$ ，费用为 $0$。 求最大费用任意流。 - $\small\blacksquare$ **模拟费用流** 考虑使用 “**增量-最大费用任意流**” 模型。  图二为新加一个点产生的边。 图三，四为可能生效的增广路、负环。 容易发现，我们的决策只有两种 ： - 选择之前较为便宜的一天买入，然后在今天卖出。 - 选择之前出售过的某一天，改为保留到今天卖出。 容易用堆维护。事实上这就是“反悔贪心”。 复杂度为 $O(n\log n)$。 ```cpp #include<algorithm> #include<cstdio> #include<queue> using namespace std; priority_queue<int> q; int n; int main() { scanf("%d",&n); long long ans=0; for (int i=1,x;i<=n;i++){ scanf("%d",&x); q.push(-x); if (x+q.top()<0)continue; ans+=x+q.top();q.pop();q.push(-x); }printf("%lld",ans); return 0; } ``` - $\large\color{blue}\bf\Delta$ [P1484 种树](https://www.luogu.com.cn/problem/P1484) **题意** ： 在一排 $n$ 个坑上种树。种在第 $i$ 个坑的收益为 $c_i$ ，但不能在相邻两个坑同时种树。 问至多种 $k$ 棵树能获得的最大收益。 - $\small\blacksquare$ **费用流模型** 为每个“间隔”建立一个点，坑则是边。 对奇数个间隔，从源点连接，容量为 $1$。对于偶数个间隔，连向汇点，容量为 $1$。 对于位置 $i$ ，两侧是间隔 $i-1,i$ ，从奇数间隔连向偶数间隔，容量为 $1$ ，费用为 $c_i$。  限制流量为 $k$ ，求最大费用任意流即可。 （有了费用流做法，就能证明该问题的凸性，然后可以使用 WQS 二分求解） - $\small\blacksquare$ **模拟费用流** 考虑直接模拟 EK 算法。 观察一次增广，会连续流过中间的若干条边（包含部分反向边，表示反悔），然后将它们的状态取反。 对应到原问题中，相当于将一个区间的树的状态取反，要求这个区间必然形如 “空【空树空树空……树】空”（中间空树严格相间，外侧必为空）。 观察可选的增广区间，如图 ：  每个极长的两边空的空树相间区间都是可选的，其余区间都不可选。只需要维护这类区间即可。 进一步观察，每次增广会将相邻的三个区间合并为一个。 用双向链表和堆维护，复杂度为 $O(n\log n)$ ，具体方法见代码。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #define Pr pair<int,int> #define fir first #define sec second #define mp make_pair #define ll long long #define MaxN 500500 using namespace std; int n,k,l[MaxN],r[MaxN],a[MaxN],tot; ll ans;bool e[MaxN]; priority_queue<Pr> t; int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++){ scanf("%d",&a[i]); t.push(mp(a[i],i)); l[i]=i-1;r[i]=i+1; } e[0]=e[n+1]=1; while(tot<k){ Pr now=t.top();t.pop(); if (now.fir<0)break; int p=now.sec; if (e[p]||now.fir!=a[p])continue; ans+=a[p];tot++; a[p]=a[l[p]]+a[r[p]]-a[p]; e[l[p]]=e[r[p]]=1; l[p]=l[l[p]];r[p]=r[r[p]]; r[l[p]]=p;l[r[p]]=p; t.push(mp(a[p],p)); }printf("%lld",ans); return 0; } ``` - $\large\color{blue}\bf\Delta$ [CF730I Olympiad in Programming and Sports](https://www.luogu.com.cn/problem/CF730I) **题意** ： 有 $n$ 个人，每个人有两个权值 $a_i,b_i$。 选出大小为 $k_1,k_2$ 的两组人 $S_1,S_2$ ，要求 $S_1∩S_2=\varnothing$。 获得的收益为 $\sum_{i\in S_1}a_i+\sum_{i\in S_2}b_i$ ，最大化这个值。 - $\small\blacksquare$ **费用流模型** 这是一个二分图费用多重匹配问题。特殊地，右部的点数非常少，只有 $2$。 - $\small\blacksquare$ **模拟费用流** 暴力讨论增广路，可以得到以下几种策略 ： - 一个没有归属的人选 $S_1$。 - 一个没有归属的人选 $S_2$。 - 一个没有归属的人选 $S_1$，一个本来在 $S_1$ 内的人改选 $S_2$。 - 一个没有归属的人选 $S_2$，一个本来在 $S_2$ 内的人改选 $S_1$。 于是用 $4$ 个堆来维护 $4$ 类可能的决策 ： - 没有归属，欲选 $S_1$ - 没有归属，欲选 $S_2$ - 已选 $S_2$，欲选 $S_1$ - 已选 $S_1$，欲选 $S_2$ 复杂度为 $O(n\log n)$。 扩展到右部点为 $k$ 个也有类似做法。 [CF评测记录](https://codeforces.com/contest/730/submission/119530159) ------------ - $\large\color{blue}\bf\Delta$ BZOJ4877 [Lydsy1708月赛]跳伞求生 （**老鼠进洞其二**） **题意** ： 有 $n$ 名玩家，第 $i$ 名玩家战斗力为 $a_i$ 。 有 $m$ 名敌人，第 $i$ 个敌人战斗力为 $b_i$ ，赏金为 $c_i$。 若 $a_i>b_j$ ，则第 $i$ 名玩家可以消灭第 $j$ 名敌人，并获得 $a_i-b_j+c_i$ 的分数。 每名玩家至多消灭一名敌人，也可以什么都不做，求最大得分。 ------------ 和“老鼠进洞其一”的建图很类似。 按照 $a,b$ 排序，从小到大添加人物。只有下列几种决策 ： - 用当前的 $a_i$ 匹配之前的某个 $b_k$。收益为 $a_i-b_k+w_k$。 - 用当前的 $a_i$ 换掉之前的某个 $a_k$。收益为 $a_i-a_k$。 用堆维护 $-b_k+w_k,-a_k$ 等决策即可。复杂度为 $O(n\log n)$。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #define ll long long #define MaxN 100500 using namespace std; const int INF=1000000000; struct Data{int x,c;}a[MaxN<<1]; bool cmp(const Data &A,const Data &B) {return A.x==B.x ? A.c<B.c: A.x<B.x;} priority_queue<int> q; int n,m; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){ scanf("%d",&a[i].x); a[i].c=-1; } for (int i=n+1;i<=n+m;i++) scanf("%d%d",&a[i].x,&a[i].c); sort(a+1,a+n+m+1,cmp); q.push(-INF); ll ans=0; for (int i=1;i<=n+m;i++) if (a[i].c==-1){ if (q.top()+a[i].x>0){ ans+=q.top()+a[i].x;q.pop(); q.push(-a[i].x); } }else q.push(a[i].c-a[i].x); printf("%lld",ans); return 0; } ``` ------------ - $\large\color{blue}\bf\Delta$ [#455. 【UER #8】雪灾与外卖](https://uoj.ac/problem/455) （老鼠进洞其三） **题意** ： 在一条直线上，有 $n$ 名送餐员与 $m$ 个餐厅。 第 $i$ 个送餐员的位置为 $x_i$。第 $i$ 家餐厅的位置为 $y_i$ ，最多生产 $c_i$ 道菜，每道菜要价 $w_i$ 元。 每个送餐员只能送一道菜，若让第 $i$ 个送餐员前往第 $j$ 个餐厅取菜，他会索要 $|x_i-y_j|$ 的报酬。 求让 $n$ 个送餐员都拿到菜的最小花费。 ------------ 建图仍然是类似的，只不过中间的边变成了双向的，而且有了费用。 为每个送餐员附加 $-\infty$ 的费用，这样才能完全转化为“最小费用任意流”。 仍然按照坐标从左到右考虑。（实际上中间的点不会既连源又连汇，这只是示意图）  在左侧很远处加很多个很差的餐厅，这样送餐员总能够全部匹配，可以忽略 $\rm III$。 接下来考虑其余 $3$ 种增广路在原问题中的意义。 注意到中间的边有正有负，意义并不明确。我们需要进一步观察原问题的性质。 - 一定存在一种最优匹配，使得交叉的匹配不存在。 显然，交叉的匹配可以调整为包含的，且不会变劣。 - 在最优匹配中，每一对匹配中间不会有未匹配的 $x$。 如果有，拿这个 $x$ 来匹配更优。 - 被匹配 $(x_i,y_j)$ 包含的所有匹配方向都与 $(x_i,j_y)$ 相同，否则可以调整更优。 因此，我们的匹配是长这样的 ： - $\rm III$ 决策有四种，分别是 ： - 对于餐厅 $i$ - 选一个前面的送餐员 $j$ 领菜。花费为 $y_i-x_j+w_i-\infty$。 - 选一个前面被取过菜的餐厅 $j$，改取自己的菜。花费为 $y_i+w_i-y_j-c_j$ - 对于送餐员 $i$ - 选一个前面的餐厅 $j$ 前往取菜。花费为 $x_i-y_j+w_j-\infty$。 - 选一个前面取过菜的送餐员，取他的菜。花费为 $x_i-x_j$。 用四个堆分别维护 : - $-x_j$ （未取菜的送餐员） - $-y_j-w_j$ （已取的菜） - $-y_j+w_j$ （未取的菜） - $-x_j$ （已取菜的送餐员） 注意餐厅有容量，故可能匹配多次。在堆中不仅要记录权值，还要记录个数。（也要记录来源地） 复杂度为 $O(n\log n)$。 ```cpp ``` ------------ - $\large\color{blue}\bf\Delta$ [P6122 [NEERC2016]Mole Tunnels](https://www.luogu.com.cn/problem/P6122) （老鼠进洞其四） **题意** ： 给出一棵 $n$ 个点的树，编号为 $1\sim n$ ，以 $1$ 为根。节点 $i\ (2\leq i\leq n)$ 的父亲为 $\lfloor i/2\rfloor$。 第 $i$ 个洞内有 $c_i$ 个食物，共有 $m$ 只鼹鼠，第 $i$ 只住在点 $p_i$。 对于所有 $k=1\sim m$ ，前 $k$ 只鼹鼠各找到一个食物，在树上行走的最小总距离。 ------------ - $\small\blacksquare$ **费用流模型** - 对于树上的每条边 $u\leftrightarrow v$ ，连边 $u\leftrightarrow v$ ，容量无限，费用为 $1$。 - 对于点 $u$ ，连边 $u\rightarrow T$ ，容量为 $c_i$ ，无权。 - 对于鼹鼠 $i$ ，连边 $S\rightarrow p_i$ ，容量为 $1$ ，无权。 求解最小费用最大流。 ------------ - $\small\blacksquare$ **模拟费用流** 首先观察建图 :  考虑将每条鼹鼠边额外加一个很小的权值 $-C$ ，然后问题就转化为最小费用任意流。 使用 “**增量-最小费用任意流**” 模型。逐个考虑鼹鼠。 由于必然满流，和 $S$ 相连的边不会退流，不会产生反向边。因此，图中不存在新的环，于是只需考虑新增的源汇路。 由于树的直径是 $O(\log n)$ 级别，可以每次找出最短增广路，并大力处理反向边。 问题不难转化为 ： - 查询到点 $u$ 的最近关键点。 - 将树上的边 $u\rightarrow v$ 的权值从 $1$ 改为 $-1$ 或者从 $-1$ 改为 $1$。 - 删除一个关键点。 设 $s[u]$ 为 $u$ 到子树内关键点的最近距离。不难用类似线段树的方法维护。 当查询时，一路向上并查看分支即可。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 100500 using namespace std; const int INF=1000000000; struct Node{int c1,c2,c,p,d;}a[MaxN]; inline void up(int u,int v){ int dl=a[v].d+(a[v].c1 ? -1 : 1); if (dl<a[u].d){a[u].d=dl;a[u].p=a[v].p;} } int n; inline void up(int u) { a[u].d=INF; if ((u<<1)<=n)up(u,u<<1); if ((u<<1|1)<=n)up(u,u<<1|1); if (a[u].c&&a[u].d>0){a[u].d=0;a[u].p=u;} } void build(int u){ if (u>n)return ; build(u<<1);build(u<<1|1);up(u); } void upd(int u){while(u){up(u);u>>=1;}} int e[MaxN],ef; void tag(int u){while(u){e[u]=ef;u>>=1;}} void mdf1(int u){while(e[u]!=ef){(a[u].c2 ? a[u].c2-- : a[u].c1++);u>>=1;}} void mdf2(int u){while(e[u]!=ef){(a[u].c1 ? a[u].c1-- : a[u].c2++);u>>=1;}} int m,ans; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)scanf("%d",&a[i].c); build(1); for (int i=1,u;i<=m;i++){ scanf("%d",&u); int v=u,dis=INF,p,sav=0; while(v){ int d=a[v].d+sav; if (dis>d){dis=d;p=a[v].p;} sav+=(a[v].c2 ? -1 : 1); v>>=1; }ans+=dis; a[p].c--; ef++;tag(p);mdf1(u); ef++;tag(u);mdf2(p); printf("%d ",ans); upd(u);upd(p); }return 0; } ``` ------------ - $\large\color{blue}\bf\Delta$ [P3826 [NOI2017] 蔬菜](https://www.luogu.com.cn/problem/P3826) 见 [题解【P3826 [NOI2017] 蔬菜】](https://www.luogu.com.cn/blog/command-block/solution-p3826) ------------ - $\large\color{blue}\bf\Delta$ [P5470 [NOI2019] 序列](https://www.luogu.com.cn/problem/P5470) 见 [题解 【P5470 [NOI2019] 序列】](https://www.luogu.com.cn/blog/command-block/solution-p5470) ------------ - [Loj#574. 「LibreOJ NOI Round #2」黄金矿工](https://loj.ac/p/574) - [Loj#6405. 「ICPC World Finals 2018」征服世界](https://loj.ac/p/6405) **题意** ： 给出一棵树，边有边权，均为正。 第 $i$ 个节点上初始时有 $x_i$ 个石子，最终需要至少 $y_i$ 个石子。 将一个石子沿某条边移动，代价为该边的边权。求完成目标所需的最小代价。 $n\leq 2.5\times 10^5,\sum x\leq 10^6$。 ------------ 为了方便，将 $x,y$ 反过来， 则模型和上一题相同。不过方法有较大区别。 仍然为每棵需要进洞的石子加权一个很小的值 $-C$。你 考虑使用 “**增量-最小费用任意流**” 模型。不需要逐个增加流量，于是可以按照任意顺序添加。 在树中由深至浅添加点，如图 ：  左 ： 红色为新增的边。 中，右 ： 可能的新增广路。不难发现，加入 $u$ 点时只需要考虑 $\rm lca$ 为 $u$ 的点对的贡献。 不能像上一题那样暴力维护反向边了，考虑继续发掘性质。 咕咕。