Liveddd's Blog

愛にできることはまだあるかい

模拟费用流

发表于 更新于 分类于
本文字数： 3.9k 阅读时长 ≈ 9 分钟

模拟费用流 学习笔记。

0.引入

之前就做过一些关于模拟网络流的题目，其大致思路一般是：1.建出网络流模型；2.尝试用数据结构来维护，或者用 贪心、DP 的思想模拟网络流 进行的过程。而且在很多图上，转化为最小割模型具有很好的性质，使求解变得容易许多。如 CF1368H2 Breadboard Capacity (hard version)，CF1408H Rainbow Triples。

模拟费用流思想是类似的，应用更广泛，常用来求解最优性。但要求网络流模型具有很好的性质：比如类二分图等等。感觉最重要的 就是对网络流模型性质的把控和挖掘了。

我们主要通过例题引入。

1.P5470 [NOI2019] 序列

首先选数配对的操作，很像二分图上的匹配。于是尝试转化为费用流，建二分图，将序列 $a$ 和 $b$ 分别作为二分图的两部，分别连向源点与汇点 $(s,a_i,1),(b_j,t,1)$，对于下标 $i=j$ 的点连边 $(a_i,b_j,1)$，新建两个点 $u,v$，代表不匹配时产生的贡献，连边 $(u,v,K-L,0),(a_i,u,1,0),(v,b_j,1,0)$。

尝试使用贪心模拟用增广路进行增广过程。我们考虑可能的增广路，主要有以下几种：

  1. $i=j$。
  2. $i \neq j$，消耗一单位的自由流量。
  3. 将 $a_i$ （未选）与 $b_i$ （已选）配对，将 $a_j$ （已选）与 $b_i$ （未选）配对，增加一单位自由流量。
  4. 将 $a_i$ （未选）与 $b_i$ （已选）配对，将 $b_j$ 与原来 $b_i$ 配对的 $a_k$。
  5. 将 $b_i$ （未选）与 $a_i$ （已选）配对，将 $a_j$ 与原来 $a_i$ 配对的 $b_k$。

我们直接用对来维护这五种转移。具体地，我们直接使用五个堆分别维护：

  1. 未选的数中 $a_i+b_i$，设为 $s$。
  2. 未选的数中 $a_i$，设为 $a$。
  3. 未选的数中 $b_i$，设为 $b$。
  4. 本侧未选中，另一侧选中的 $a_i$，设为 $a’$。
  5. 本侧未选中，另一侧选中的 $b_i$，设为 $b’$。

那么对应的五种转移为：

  1. $s$。
  2. $a+b$，减少一单位自由流量。
  3. $a’+b’$，增加一单位自由流量。
  4. $a’+b$。
  5. $a+b’$。

注意维护过程中操作优先级 $(1)>(3)>(4)=(5)>(2)$。最终时间复杂度为 $\mathcal O((n+k)\log n)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<queue>
#define fi first
#define se second
using namespace std;
using ll=long long;
using PII=pair<int,int>;
const int N=2e5+10,INF=1e9+10;
template <class T>
inline void read(T &x)
{
	x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int T,n,k,l;
int a[N],b[N];
bool va[N],vb[N];
ll ans;
priority_queue<PII>q[5];
inline void geta(int i){if(!vb[i])q[4].push({b[i],i});}
inline void getb(int i){if(!va[i])q[3].push({a[i],i});}
inline void solve()
{
    read(n,k,l);
    ans=0;
    for(int i=0;i<5;i++)while(!q[i].empty())q[i].pop();
    for(int i=1;i<=n;i++)read(a[i]),va[i]=0;
    for(int i=1;i<=n;i++)read(b[i]),vb[i]=0;
    for(int i=1;i<=n;i++)q[0].push({a[i]+b[i],i}),q[1].push({a[i],i}),q[2].push({b[i],i});
    while(k--)
    {
        int type=-1,res=-INF;
        int s=-INF,fa=-INF,fb=-INF,sa=-INF,sb=-INF;
        while(!q[0].empty()&&(va[q[0].top().se]||vb[q[0].top().se]))q[0].pop();
        if(!q[0].empty())s=q[0].top().fi;
        while(!q[1].empty()&&va[q[1].top().se])q[1].pop();
        if(!q[1].empty())fa=q[1].top().fi;
        while(!q[2].empty()&&vb[q[2].top().se])q[2].pop();
        if(!q[2].empty())fb=q[2].top().fi;
        while(!q[3].empty()&&(va[q[3].top().se]||!vb[q[3].top().se]))q[3].pop();
        if(!q[3].empty())sa=q[3].top().fi;
        while(!q[4].empty()&&(!va[q[4].top().se]||vb[q[4].top().se]))q[4].pop();
        if(!q[4].empty())sb=q[4].top().fi;

        if(l<=k&&fa+fb>=res)res=fa+fb,type=1;
        if(fa+sb>=res)res=fa+sb,type=2;
        if(sa+fb>=res)res=sa+fb,type=3;
        if(sa+sb>=res)res=sa+sb,type=4;
        if(s>=res)res=s,type=0;
        
        if(type==-1)break;
        ans+=res;
        if(type==0)va[q[0].top().se]=vb[q[0].top().se]=1,l--;
        if(type==1)va[q[1].top().se]=vb[q[2].top().se]=1,geta(q[1].top().se),getb(q[2].top().se);
        if(type==2)va[q[1].top().se]=vb[q[4].top().se]=1,l--,geta(q[1].top().se);
        if(type==3)va[q[3].top().se]=vb[q[2].top().se]=1,l--,getb(q[2].top().se);
        if(type==4)va[q[3].top().se]=vb[q[4].top().se]=1,l-=2;        
    }
    printf("%lld\n",ans);
}
int main()
{
    read(T);
    while(T--)solve();
    return 0;
}

上面的思考过程其实比较套路。但这已经是模拟费用流的普遍的做法了。真正困难的点在于，对费用流模型性质的挖掘，或者是对增广路性质的挖掘。

2.P4189 [CTSC2010]星际旅行