看到 cmd 的博客之后对模拟费用流有了新的理解。
模拟费用流，实际上是对于某些特殊的费用流建模模拟跑费用流的过程，复杂度比直接跑费用流要低许多。
首先费用流是个凸函数，因为根据 EK，增广路长度不断增长，则费用是关于流量的凸函数。
然后是模拟费用流通常解决的问题：最小 / 大费用任意流。以最小为例。正常跑 EK 的时候是每次增广最短路，单次费用正时停止。在模拟费用流中，我们通常采用每次增加一些点和边，并考虑新的“源点到汇点的负路径”和“负环”的贡献。
用一些例题来表明一下大概是个什么过程。
P4694 [PA2013] Raper
经验：CF802O，CF802N。
连边是显然的：源点向 \(a_i\) 连 \((1,a_i)\)，\(b_i\) 向汇点连 \((1,b_i)\)，然后每个 \(a_i\) 向 \(j\ge i\) 的 \(b_j\) 连 \((1,0)\)。然后限制总流量 \(k\)。
这个限制有点难受，WQS 二分一下消掉。那么所有的 \(a_i\) 要减掉一个 \(C\)。
顺序考虑 \(1-n\) 的所有 \(b\)。此时有如下几种可能的负路径和负环：
- \(S\to a_i\to b_i\to T\) 的负路径。
- 对于 \(j<i\)，\(a_j\to b_i\to T\to b_j\to a_j\) 的负环。
对应到原问题上就是两个操作：当前 \(A\) 匹配当前 \(B\)，之间的 \(A\) 把之间的 \(B\) 反悔掉匹配当前 \(B\)。可以直接用两个堆维护。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
struct node{
int val;bool jud;
bool operator<(const node &s)const{
return val==s.val?jud>s.jud:val>s.val;
}
};
int n,k,ans,a[500010],b[500010];
pair<int,int> check(int mid){
int cnt=0,ans=0;
priority_queue<node>q;
for(int i=1;i<=n;i++){
q.push({a[i],true});
node ret=q.top();
int val=b[i]+ret.val-mid;
if(val>=0)continue;
ans+=val,cnt+=ret.jud;q.pop();
q.push({mid-b[i],false});
}
return make_pair(cnt,ans);
}
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
int l=0,r=2147483647;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid).first<=k)l=mid;
else r=mid-1;
}
ans=check(l).second+l*k;
printf("%lld\n",ans);
return 0;
return 0;
}
CF865D Buy Low Sell High
建图：源点向每天连 \((1,-c_i)\)，每天向汇点连 \(1,c_i\)，每天向第二天连 \(\infty,0\)。
现在要费用最大，那么考虑正路径和正环。顺序扫每一天，考虑新增的路径和环：
- \(S\to i\to T\) 的路径。一开始先默认他流着。
- \(S\to j\to i\to S\) 的环。这玩意是用来退掉之前的流的，也就是把之前的某一天买进的放到今天卖。
- \(T\to j\to i\to T\) 的环。也就是把之前某天卖出的不卖，放到今天卖。
同样可以堆维护。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
int n,ans;
priority_queue<int,vector<int>,greater<int> >q;
signed main(){
scanf("%lld",&n);
int cnt=1;
for(int i=1;i<=n;i++){
int x;scanf("%lld",&x);
if(!q.empty()&&x>q.top()){
ans+=x-q.top();q.pop();q.push(x);
}
q.push(x);
}
printf("%lld\n",ans);
return 0;
}
P1484 种树
同样容易建出费用流模型：二分图，左边奇右边偶，相邻连边。限制流量 \(k\)。
同样可以 WQS 二分，但考虑另一种做法：直接模拟 EK。
观察一次增广，会连续流过中间的若干边再流到汇点。那么就相当于将一个区间的状态取反，且要求必须状态 \(01\) 相间且两头为 \(0\)。操作一次也就相当于把这个区间和两边区间合并，使用堆 + 链表即可做到一个 \(\log\)。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
priority_queue<pair<int,int> >q;
int n,k,ans,a[500010],l[500010],r[500010];
bool vis[500010];
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),l[i]=i-1,r[i]=i+1,q.push(make_pair(a[i],i));
int cnt=0;
while(cnt<k){
pair<int,int>p=q.top();q.pop();
if(p.first<0)break;
if(vis[p.second]||p.first!=a[p.second])continue;
ans+=p.first;cnt++;
vis[l[p.second]]=vis[r[p.second]]=true;
a[p.second]=a[l[p.second]]+a[r[p.second]]-a[p.second];
l[p.second]=l[l[p.second]],r[p.second]=r[r[p.second]];
r[l[p.second]]=l[r[p.second]]=p.second;
q.push(make_pair(a[p.second],p.second));
}
printf("%lld\n",ans);
return 0;
}
P6122 [NEERC2016] Mole Tunnels
模型搬到了树上。
仍然容易建出费用流模型：源点向 \(p_i\) 连 \((1,0)\)，每个点向汇点连 \((c_i,0)\)，树边相互连 \((\infty,1)\)，跑最小费用最大流。
遇到这种最大流的，先假装给所有源点向 \(p_i\) 连的边有个 \(-\infty\) 的权值，就变成了最小费用任意流。实际代码上不用实现这一步。
这时候必然满流，于是和 \(S\) 相连的边不会退流。于是只要找到一个点和哪个点在树上距离最近。一次增广需要把目标点的 \(c\) 减 \(1\)，同时把所有路径上的单向边的权值改成 \(-1\) 表示退流。树高是 \(O(\log n)\)，可以直接暴力。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;
int n,m,ans,c[100010];
struct node{
#define lson rt<<1
#define rson rt<<1|1
int pos,dis,u,d;
}tree[100010];
void upd(int rt,int son){
int val=tree[son].dis;
if(tree[son].d)val--;
else val++;
if(val<tree[rt].dis)tree[rt].dis=val,tree[rt].pos=tree[son].pos;
}
void pushup(int rt){
tree[rt].dis=0x3f3f3f3f;
if((lson)<=n)upd(rt,lson);
if((rson)<=n)upd(rt,rson);
if(c[rt]&&tree[rt].dis>0)tree[rt].dis=0,tree[rt].pos=rt;
}
int id,vis[100010];
void update(int x,int y){
int ret=y;
id++;
while(ret)vis[ret]=id,ret>>=1;
ret=x;
while(ret&&vis[ret]!=id){
if(tree[ret].u)tree[ret].u--;
else tree[ret].d++;
ret>>=1;
}
ret=x;id++;
while(ret)vis[ret]=id,ret>>=1;
ret=y;
while(ret&&vis[ret]!=id){
if(tree[ret].d)tree[ret].d--;
else tree[ret].u++;
ret>>=1;
}
}
void build(int rt){
if((lson)<=n)build(lson);
if((rson)<=n)build(rson);
pushup(rt);
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
build(1);
for(int i=1;i<=m;i++){
int p;scanf("%lld",&p);
int val=0x3f3f3f3f,dis=0,pos,x=p;
while(p){
if(tree[p].dis+dis<val)val=tree[p].dis+dis,pos=tree[p].pos;
if(tree[p].u)dis--;
else dis++;
p>>=1;
}
ans+=val;c[pos]--;
printf("%lld ",ans);
update(x,pos);
while(x)pushup(x),x>>=1;
while(pos)pushup(pos),pos>>=1;
}
puts("");
return 0;
}