模拟费用流小记

· · 个人记录

0. 概论

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

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

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

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

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

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

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

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

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

2. 经典例题

从源点向每天的 A 厂连边，容为 1 ，费用为 a_i。

从每天的 B 厂向汇点连边，容为 1 ，费用为 b_i。

从第 i 天的 A 厂向 i\leq j\leq n 的第 j 天的 B 厂连边。

限制源的总流量为 k。

不难发现，这是一个类似于费用匹配的问题。

这是市面上流传较广的解法。

费用流告诉我们，这个问题的答案关于 k 有凸性，故可以使用 WQS 二分来优化。

在二分惩罚 C 之后，只需要给全体 a_i 加上 C。此时不需要再考虑 k 的约束。

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

依次考虑 a_n...a_1 ，它们能匹配的 b 的集合依次增大。相当于在图上依次增加点。

考虑新加入的两个点以及相关的边能引出怎样的 “源到汇的路径” 以及 “环” ：

如图 I ，红色边为新加入的边（方向确定），黑色边为旧的边，方向是不确定的（可能由于增广而反向）

上述合法的两种决策容易用堆维护（注意还需维护匹配个数），故复杂度为 O(n\log^2n)。

考虑直接模拟 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 时的答案。

评测记录

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

从源点向每天连边，容为 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;
}

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

对奇数个间隔，从源点连接，容量为 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;
}

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

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

于是用 4 个堆来维护 4 类可能的决策 ：

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

扩展到右部点为 k 个也有类似做法。

CF评测记录

和“老鼠进洞其一”的建图很类似。

按照 a,b 排序，从小到大添加人物。只有下列几种决策 ：

用堆维护 -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;
}

建图仍然是类似的，只不过中间的边变成了双向的，而且有了费用。

为每个送餐员附加 -\infty 的费用，这样才能完全转化为“最小费用任意流”。

仍然按照坐标从左到右考虑。（实际上中间的点不会既连源又连汇，这只是示意图）

在左侧很远处加很多个很差的餐厅，这样送餐员总能够全部匹配，可以忽略 \rm III。

接下来考虑其余 3 种增广路在原问题中的意义。

注意到中间的边有正有负，意义并不明确。我们需要进一步观察原问题的性质。

因此，我们的匹配是长这样的 ：

决策有四种，分别是 ：

用四个堆分别维护 :

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

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

求解最小费用最大流。

首先观察建图 :

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

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

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

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

问题不难转化为 ：

设 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] 序列】

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

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

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

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

左 ： 红色为新增的边。

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

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

咕咕。