0. 概论

费用流问题是 OI 中的一个应用广泛的经典模型，可以解决种类繁多的最优化问题，以思路巧妙，变化多端著称。

然而，与良好的普适性相对，费用流常用算法的效率较为低下，只能处理较小的数据范围。

在一些特殊的费用流模型中，可以利用题目的特殊性质，结合数据结构等技巧，设计更高效的费用流算法，称之为“模拟费用流”。

这种思路先将原问题转化为费用流问题，再进一步转化成其他更简化的（数据结构）问题。

其中，费用流模型扮演了关键的桥梁角色，帮助我们规范分析，洞察性质，并施展积累的经验技巧。

• 参考资料

  • 陈江伦（laofu） WC2019 讲义 《模拟费用流问题》

1. 费用流模型与常用性质

费用流基础知识可见 : 网络流/二分图相关笔记(干货篇)

下面也开列一些有用的事实。

为了便于叙述，默认为最小费用流。

• 费用流经典算法

  • EK : 每次寻找最短的增广路进行增广。（ zkw和EK本质相同，只是实现方式不同 ）

  • 消圈 : 先随意求出一个流，然后不断消去图中的负环。

  可以直接模拟上述算法的思路，也可以基于这些算法的正确性，设计类似的规则。

• 费用流的凸性

  根据 EK 算法，增广路的长度会不断增长，则费用是关于流量的凸函数。

• 费用流问题的变形

  • 最小费用任意流 : 可用 EK 求解，每次增广最短路，当单次费用为正时停止。

  • 负费用最大流 : 可用 EK 求解，每次增广最短路，当总费用非正时停止。

  上述做法由凸性易证正确性。

  • 增量-最小费用任意流 : 每次在图中增加一些点和边，并求解新的最小费用任意流。

    只需考虑所有新的 “源到汇的负路径” 以及 “负环” 的贡献。

    也可以看做源和汇之间有容量为无穷的边连接，这样“源到汇的负路径”实际上就是“负环”。

• 经典结论

  • 在非增量费用流中，源汇边不会退流。

  • 增广路不会多次经过同一个点。

2. 经典例题

• **题意** ： 你需要生产 $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:) ，分两类讨论。

使用线段树维护，对于区间 [l,r]，记录下列值 :

具体转移见代码。

由于 S_{1\sim n} 必定 \geq 0 ，且 S_n 恒为 0 ，故每次取出节点 [1,n] 的 ans1,ans3 中的较优解。

复杂度 O(n+k\log n)。

此做法能分别求出 k=1\sim n 时的答案。

评测记录

• CF865D Buy Low Sell High （老鼠进洞其一）

  题意 ： 已知接下来 n 天的股票价格 c_i，每天你可以买进一股股票，卖出一股股票，或者什么也不做。

  假设你拥有无限本金，求 n 天之后能得到的最大利润。

这也是一个费用匹配问题。

从源点向每天连边，容为 1 ，费用为 -c_i。

从每天向汇点连边，容为 1 ，费用为 c_i。

每天向第二天连边，容为 +\infty ，费用为 0。

求最大费用任意流。

考虑使用 “增量-最大费用任意流” 模型。

图二为新加一个点产生的边。

图三，四为可能生效的增广路、负环。

容易发现，我们的决策只有两种 ：

• 选择之前较为便宜的一天买入，然后在今天卖出。

• 选择之前出售过的某一天，改为保留到今天卖出。

容易用堆维护。事实上这就是“反悔贪心”。

复杂度为 O(n\log n)。

#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;
}

• **题意** ： 在一排 $n$ 个坑上种树。种在第 $i$ 个坑的收益为 $c_i$ ，但不能在相邻两个坑同时种树。 问至多种 $k$ 棵树能获得的最大收益。

为每个“间隔”建立一个点，坑则是边。

对奇数个间隔，从源点连接，容量为 1。对于偶数个间隔，连向汇点，容量为 1。

对于位置 i ，两侧是间隔 i-1,i ，从奇数间隔连向偶数间隔，容量为 1 ，费用为 c_i。

限制流量为 k ，求最大费用任意流即可。

（有了费用流做法，就能证明该问题的凸性，然后可以使用 WQS 二分求解）

考虑直接模拟 EK 算法。

观察一次增广，会连续流过中间的若干条边（包含部分反向边，表示反悔），然后将它们的状态取反。

对应到原问题中，相当于将一个区间的树的状态取反，要求这个区间必然形如 “空【空树空树空……树】空”（中间空树严格相间，外侧必为空）。

观察可选的增广区间，如图 ：

每个极长的两边空的空树相间区间都是可选的，其余区间都不可选。只需要维护这类区间即可。

进一步观察，每次增广会将相邻的三个区间合并为一个。

用双向链表和堆维护，复杂度为 O(n\log n) ，具体方法见代码。

#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;
}

• **题意** ： 有 $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$ ，最大化这个值。

这是一个二分图费用多重匹配问题。特殊地，右部的点数非常少，只有 2。

暴力讨论增广路，可以得到以下几种策略 ：

• 一个没有归属的人选 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评测记录

• **题意** ： 有 $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)。

#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;
}

• **题意** ： 在一条直线上，有 $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。

用四个堆分别维护 :

注意餐厅有容量，故可能匹配多次。在堆中不仅要记录权值，还要记录个数。（也要记录来源地）

复杂度为 O(n\log n)。

• **题意** ： 给出一棵 $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$ 只鼹鼠各找到一个食物，在树上行走的最小总距离。

• 对于树上的每条边 u\leftrightarrow v ，连边 u\leftrightarrow v ，容量无限，费用为 1。

• 对于点 u ，连边 u\rightarrow T ，容量为 c_i ，无权。

• 对于鼹鼠 i ，连边 S\rightarrow p_i ，容量为 1 ，无权。

求解最小费用最大流。

首先观察建图 :

考虑将每条鼹鼠边额外加一个很小的权值 -C ，然后问题就转化为最小费用任意流。

使用 “增量-最小费用任意流” 模型。逐个考虑鼹鼠。

由于必然满流，和 S 相连的边不会退流，不会产生反向边。因此，图中不存在新的环，于是只需考虑新增的源汇路。

由于树的直径是 O(\log n) 级别，可以每次找出最短增广路，并大力处理反向边。

问题不难转化为 ：

• 查询到点 u 的最近关键点。

• 将树上的边 u\rightarrow v 的权值从 1 改为 -1 或者从 -1 改为 1。

• 删除一个关键点。

设 s[u] 为 u 到子树内关键点的最近距离。不难用类似线段树的方法维护。

当查询时，一路向上并查看分支即可。

#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;
}

见 题解【P3826 [NOI2017] 蔬菜】

见 题解 【P5470 [NOI2019] 序列】

• Loj#574. 「LibreOJ NOI Round #2」黄金矿工

• Loj#6405. 「ICPC World Finals 2018」征服世界

  题意 ： 给出一棵树，边有边权，均为正。

  第 i 个节点上初始时有 x_i 个石子，最终需要至少 y_i 个石子。

  将一个石子沿某条边移动，代价为该边的边权。求完成目标所需的最小代价。

为了方便，将 x,y 反过来， 则模型和上一题相同。不过方法有较大区别。

仍然为每棵需要进洞的石子加权一个很小的值 -C。你

考虑使用 “增量-最小费用任意流” 模型。不需要逐个增加流量，于是可以按照任意顺序添加。

在树中由深至浅添加点，如图 ：

左 ： 红色为新增的边。

中，右 ： 可能的新增广路。不难发现，加入 u 点时只需要考虑 \rm lca 为 u 的点对的贡献。

不能像上一题那样暴力维护反向边了，考虑继续发掘性质。

咕咕。