学习笔记 - 费用流

最近开始了网络流的魔鬼练习,出现了一堆脑洞题(我现在脑袋已经要变成一个杯子形了 QwQ)

新学了一些网络流的方法,写一下博客免得忘掉……


Part1. 费用流的概念

目前碰到了两种费用流:最小费用最大流、最大费用最大流

费用流的流网络上,边 $(u,v)$ 除了容量,还有一个费用cost,这意味着如果这条边上的流量为flow,这条边就会产生flow*cost的费用。而且cost满足斜对称性,即cost[u,v]=-cost[v,u]

最小费用最大流就是在满足流量最大的基础上,使得总费用最小(最大费用最大流则是使费用最大)。


Part2. 最小费用最大流

这种费用流的实现方法由 Dinic 改变得到 —— 普通的 Dinic 分层用 BFS() ,其实相当于每条边的费用都是 1,因此没有影响,但是对于费用流,每条边的费用可能不同,因此要将 BFS() 改为 SPFA()(虽然,关于 SPFA(),它死了……但是大部分题实测仍然跑得很快),这里用 SPFA() 主要是因为存在负费用(正向边的费用是正数,则反向边就是负数了)。

Tab. 有一种尴尬的情况,如果建图的时候,正向边形成了负权环,就要用最小费用循环流(没学过,先写着,留个坑之后再填)。不过很开心的是除了这种情况,费用流是不会出现负权环的 awa

具体的话,我们用 SPFA()残留网络 上跑出从源点到每个点 $u$ 的最短路,记为 $dis(u)$。那么在增广时,只有当 $dis(u)+cost(u,v)=dis(v)$ 时,才考虑增广边 $(u,v)$(就像普通的 Dinic 分层一样)。

不放模板题了,下面来看一道有意思的题——

- [ZJOI2010]网络扩容 <洛谷>

= 题意

给出一个 $n$ 个点 $m$ 条边的有源汇流网络,源点为 $1$,汇点为 $n$,记最大流的流量为 $A$。对于流网络上的边 $(u,v)$ ,你可以花费 $cost(u,v)$ 的代价让这条边的容量 $+1$(可以增加多次)。

给出每一个 $cost(u,v)$ 和整数 $k$,求要使流网络的最大流变为 $A+k$,增加边的容量的总代价最小是多少。

(输出 $A$ 和最小代价)

= 规模

$n\leq1000$,$m\leq5000$,$k\leq10$。

= 题解

求解 $A$ 可以直接跑最大流。然后考虑求解最小代价。

设原流网络上边 $(u,v)$ 的容量为 $c(u,v)$。

我们可以这样理解题意,对于每一条边 $(u,v)$,分段计价:流量在 $0$ 到 $c(u,v)$ 时,费用为 $0$;当流量大于 $c(u,v)$ 时,超过 $c(u,v)$ 的流量费用为 $cost(u,v)$ 。即在 $(u,v)$ 之间连一条容量为 $c(u,v)$、费用为 $0$ 的边,和另一条容量为 $k$(你也可以让流量为 $\inf$,但是不难发现只需要增加 $k$ 的容量即可)、费用为 $cost(u,v)$ 的边。

最后再连一条容量为 $A+k$、费用为 $0$ 的边 $(n,n+1)$,并把 $n+1$ 作为汇点,以限制最大流只增加 $k$。再求从 $1$ 到 $n+1$ 的最小费用最大流。

然后这样建图就可以了,因为 $0<cost(u,v)$ ,所以对于每一条边,一定会先流满费用为 $0$ 的边,然后再流费用为 $cost(u,v)$ 的边。

= 源代码

【有一点长……点击展开/折叠代码
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1000,M=5000,inf=(1<<29);

struct EDGE{int to,lim,cst;EDGE *rev,*nxt;}*cpy[N+3];
struct FLOWGRAPH{
EDGE edg[5*M+10],*ncnt,*top[N+3];
FLOWGRAPH(){ncnt=edg;}
void AddEdge(int u,int v,int lim,int cst){
EDGE *p=++ncnt,*q=++ncnt;
*p=(EDGE){v,lim,cst,q,top[u]};top[u]=p;
*q=(EDGE){u,0,-cst,p,top[v]};top[v]=q;
}
}Gflw,cpyGflw;
struct PAIR{
int x,y;
PAIR(){}
PAIR(int _x,int _y):x(_x),y(_y){}
PAIR operator +(const PAIR curb)const{return (PAIR){x+curb.x,y+curb.y};}
PAIR operator +=(const PAIR curb){x+=curb.x;y+=curb.y;return *this;}
};

int n,m,Vk,Ps,Pt;
int sav[M+3][3],dis[N+3];
bool vis[N+3];

bool SPFA(){
for(int i=1;i<=Pt;i++) vis[i]=false,dis[i]=inf;
dis[Ps]=0;
queue<int> que;que.push(Ps);
while(!que.empty()){
int u=que.front();que.pop();
vis[u]=false;
for(EDGE *it=Gflw.top[u];it;it=it->nxt){
if(!it->lim) continue;
int v=it->to;
if(dis[v]>dis[u]+it->cst){
dis[v]=dis[u]+it->cst;
if(!vis[v]){
vis[v]=true;
que.push(v);
}
}
}
}
return dis[Pt]!=inf;
}
PAIR GetFlow(int u,int flwin){
if(u==Pt) return PAIR(flwin,0);
PAIR flwres=PAIR(0,0);
vis[u]=true;
for(;cpy[u];cpy[u]=cpy[u]->nxt){
if(!cpy[u]->lim) continue;
int v=cpy[u]->to;
if(!vis[v] && dis[v]==dis[u]+cpy[u]->cst){
PAIR flw=GetFlow(v,min(flwin-flwres.x,cpy[u]->lim));
flw.y+=flw.x*cpy[u]->cst;
flwres+=flw;
cpy[u]->lim-=flw.x;cpy[u]->rev->lim+=flw.x;
if(flwin==flwres.x) break;
}
}
vis[u]=false;
return flwres;
}
PAIR Dinic(){
PAIR res=PAIR(0,0);
while(SPFA()){
memcpy(cpy,Gflw.top,sizeof Gflw.top);
res+=GetFlow(Ps,inf);
}
return res;
}
int main(){
scanf("%d%d%d",&n,&m,&Vk);
Ps=1;Pt=n;
for(int i=1;i<=m;i++){
int u,v,lim,cst;
scanf("%d%d%d%d",&u,&v,&lim,&cst);
Gflw.AddEdge(u,v,lim,0);
sav[i][0]=cst;
sav[i][1]=u;
sav[i][2]=v;
}
cpyGflw=Gflw;
PAIR res=Dinic();
printf("%d ",res.x);
Gflw=cpyGflw;
for(int i=1;i<=m;i++)
Gflw.AddEdge(sav[i][1],sav[i][2],Vk,sav[i][0]);
Pt++;
Gflw.AddEdge(n,Pt,res.x+Vk,0);
res=Dinic();
printf("%d\n",res.y);
return 0;
}

= 总结-建图套路

也不算什么套路……

分段计价,对于边 $(u,v)$,设计费分为 $k$ 段,第 $i$ 段的费用为 $cost(u,v,i)$。

如果满足 $cost(u,v,i-1)\leq cost(u,v,i)$,则可以按照上面的建图方式。但是这样建图的缺点是会造成总边数变大,降低算法效率。

Part3. 最大费用最大流

个人觉得这里的费用应该被称为价值更合适,毕竟一般是要“总价值”最大。

发现上面的最小费用最大流是把费用当作边的长度,用 SPFA() 跑最短路;然后就在想,是不是把费用当边长,然后跑一个 最长路 就可以了?

的确是这样,但是并没有 最长路 这个东西,不过我们可以把边权全部取负,于是就可以跑最短路了!但是这里仍然有负权环的问题(然而这个菜博主并不会解决这个问题),先不考虑这个。SPFA() 可以跑负边,所以这个问题也就迎刃而解了~

However,如果一个非常 nice的出题人他非要卡 SPFA…… 那么我们就不得不用复杂度非常稳定为 $O(n\log n) $ 的堆优化 Dijkstra(),但是并不是直接把 SPFA() 换成 Dijkstra() 就可以的,因为这里有负权边啊 QwQ。于是我们引入一个叫做势函数的东西……

Tab. 下文有关势函数的叙述很有可能不规范,只是方便理解(不要被势函数这个陌生名词吓到了,学 Splay 的时候你还碰到过它……)

对于流网络上的每一个点 $u$ ,定义 $h(u)$ 是 $u$ 的势函数。记边 $(u,v)$ 的费用,即长度为 $l(u,v)$ 。对于每条边 $(u,v)$ 我们再定义一个附加势函数的长度 $l’(u,v)=l(u,v)+h(u)-h(v)$ ,那么我们现在就是要维护势函数的值,使得 $l’(u,v)\ge0$。

下面给出一种维护方案:

  1. $h(u)$ 的初值全设为 $0$;

  2. 首先每条边以 $l(u,v)$(原图的边权,可能有负),用 SPFA 先跑一遍,得到最初源点到每个点 $u$ 的最短距离,记作 $d(u)$,如果源点无法到达汇点,直接结束;

  3. 增广一次;

  4. 将每个 $h(u)$ 的值加上 $d(u)$,此时 $h(u)=d(u)$;

  5. 循环:

    • 每条边的边权设为 $l’(u,v)=l(u,v)+h(u)-h(v)$,然后用 Dijkstra 跑一遍得到新的 $d(u)$ ,如果从源点无法到达汇点,退出循环;

    • 增广一次;

    • 将每个 $h(u)$ 的值 加上 $d(u)$。

这样就可以保证 在跑 Dijkstra 的时候,新的边权 $l’(u,v)$ 都是非负权

证明如下:

当一条边在残留网络上,称为“这条边存在”(满流的边则“不存在”);我们只需要讨论在残留网络上的边,因为我们是在残留网络上跑最短路,所以不在残留网络上的边没有影响。

分类讨论:

  1. 边 $(u,v)$ 在增广之前在残留网络上,增广后仍有容量剩余(即仍然存在):

    由于最短路的性质,满足 $d(u)+l’(u,v)\ge d(v)$,即考虑从源点到 $v$ 的最短路可能经过 $(u,v)$,则最短路为 $d(u)+l’(u,v)$,否则存在一条更短的路径到达 $v$,因此为 $\ge$ 。

    因为 $l’(u,v)=l(u,v)+h(u)-h(v)$,所以 $d(u)+l(u,v)+h(u)-h(v)\ge d(v)$;

    移项可得 $d(u)+h(u)-d(v)-h(v)+l(u,v)\ge 0$;

    则 $[d(u)+h(u)]-[d(v)+h(v)]+l(u,v)\ge0$;

    所以让每个 $h(u)+=d(u)$ 就可以让边权非负。

  2. 边 $(u,v)$ 在增广之前不存在,增广后存在:

    由于增广的性质,可以得到反向边 $(v,u)$ 被增广,说明源点到 $u$ 的最短路经过 $(v,u)$ 这条边(因为只有最短路上的边才会被增广);

    可以得到 $d(u)=d(v)+l’(v,u)$ ;

    则 $d(u)=d(v)+l(v,u)+h(v)-h(u)$;

    移项可得 $l(v,u)+[h(v)+d(v)]-[h(u)+d(u)]=0$;

得证,“每次增广过后维护 $h(u)+=d(u)$ ”的方法,可以使得在残留网络上的边权非负。

于是放一道非常nice的出题人的题……

- [HDU多校赛2019] K Subsequence

= 题意

给出一个长度为 $n$ 的序列 $A$,你可以进行至多 $k$ 次操作:每次操作取出一个不降子序列(取出的数字就不能再取了),这次操作获得的得分为子序列中所有元素之和。

问至多 $k$ 次操作后,获得的得分之和最大为多少。

= 规模

$1\leq T\leq5$,$1\leq n\leq 2000$,$1\leq k\leq 10$,$1\leq ai\leq 10^5$

= 题解

建图非常容易理解:先给序列的每个数拆点(因为每个数只能被取出一次),第 $i$ 个数对应的点为 $i$ 和 $i+n$,除此之外再建立 $3$ 个特殊点 $S,T,M$。

建边:

  1. $i$ 连向 $i+n$ ,容量为 $1$ ,费用为 $A_i$,有流量代表 $A_i$ 被取出;
  2. $S$ 连向 $i$,容量为 $1$,费用为 $0$;
  3. $i+n$ 连向 $M$,容量为 $1$,费用为 $0$;
  4. $M$ 连向 $T$,容量为 $k$,费用为 $0$,用来限制”最多只能进行 $k$ 次操作”;
  5. 如果 $i<j$ 且 $A_i\leq A_j$,则 $i+n$ 连向 $j$,表示在一次操作中,$A_i,A_j$ 可以同时取出。

然后跑一个 $S$ 为源 $T$ 为汇的最大费用最大流即可。

然而卡 SPFA,需要用 Dijkstra 优化……就用上文提及的势函数。

= 总结 - 一个简单的建图技巧

如果建图后要求“限制某一个的流量”,就可以拆点,把一个点 $u$ 拆为入点 $u_0$ 和出点 $u_1$。然后在 $u_1,u_0$ 之间连容量为限制流量最大值的边。

= 模板

【这道题真的可以当作模板-点击展开/折叠代码
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/*Lucky_Glass*/
#pragma GCC optimize(2)
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=4003;

struct EDGE{int to,lim,cst,rev;};

struct PAIR{
int fir,sec;
PAIR(){fir=sec=0;}
PAIR(int _f,int _s):fir(_f),sec(_s){}
PAIR operator +=(const PAIR Vb){fir+=Vb.fir;sec+=Vb.sec;return *this;}
bool operator >(const PAIR Vb)const{return (fir==Vb.fir)? (sec>Vb.sec):(fir>Vb.fir);}
};

const int inf=(1<<29);
int cas,n,m,Ps,Pt,Pm;
vector<EDGE> lnk[N+3];
int Ca[N+3],cpy[N+3],Ch[N+3],dis[N+3];
bool firstSPFA;
bool vis[N+3];

void SPFA(){
queue<int> que;
que.push(Ps);vis[Ps]=true;dis[Ps]=0;
while(!que.empty()){
int u=que.front();que.pop();
vis[u]=false;
for(int i=0;i<(int)lnk[u].size();i++){
if(lnk[u][i].lim<=0) continue;
int v=lnk[u][i].to;
if(dis[v]>dis[u]+lnk[u][i].cst){
dis[v]=dis[u]+lnk[u][i].cst;
if(!vis[v]){
que.push(v);
vis[v]=true;
}
}
}
}
}
void Dijkstra(){
priority_queue< PAIR,vector<PAIR>,greater<PAIR> > que;
que.push(PAIR(dis[Ps]=0,Ps));
while(!que.empty()){
int u=que.top().sec;que.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=0;i<(int)lnk[u].size();i++){
if(lnk[u][i].lim<=0) continue;
int v=lnk[u][i].to;
if(dis[v]>dis[u]+Ch[u]-Ch[v]+lnk[u][i].cst){
dis[v]=dis[u]+Ch[u]-Ch[v]+lnk[u][i].cst;
que.push(PAIR(dis[v],v));
}
}
}
for(int i=1;i<=Pm;i++) vis[i]=false;
}
bool Update(){
for(int i=1;i<=Pm;i++) dis[i]=inf,cpy[i]=vis[i]=0;
if(firstSPFA) firstSPFA=false,SPFA();
else Dijkstra();
return dis[Pt]!=inf;
}
int GetFlow(int u,int flwin){
if(u==Pt) return flwin;
int flwout=0;
vis[u]=true;
for(;cpy[u]<(int)lnk[u].size();cpy[u]++){
int it=cpy[u];
if(!lnk[u][it].lim) continue;
int v=lnk[u][it].to;
if(!vis[v] && dis[u]+lnk[u][it].cst+Ch[u]-Ch[v]==dis[v]){
int flwv=GetFlow(v,min(flwin-flwout,lnk[u][it].lim));
flwout+=flwv;
lnk[u][it].lim-=flwv;
lnk[v][lnk[u][it].rev].lim+=flwv;
if(flwin==flwout) break;
}
}
vis[u]=false;
return flwout;
}
int Dinic(){
int ret=0;
firstSPFA=true;
while(Update()){
ret+=(dis[Pt]+Ch[Pt])*GetFlow(Ps,inf);
for(int i=1;i<=Pm;i++)
if(dis[i]!=inf)
Ch[i]+=dis[i];
}
return ret;
}
void AddEdge(int u,int v,int lim,int cst){
int p=lnk[u].size(),q=lnk[v].size();
lnk[u].push_back((EDGE){v,lim,cst,q});
lnk[v].push_back((EDGE){u, 0,-cst,p});
}
int main(){
// freopen("multi.in","r",stdin);
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&Ca[i]);
Ps=2*n+1,Pt=Ps+1;Pm=Pt+1;
for(int i=1;i<=Pm;i++) lnk[i].clear(),Ch[i]=0;
for(int i=1;i<=n;i++){
AddEdge(Ps,i,1,0);
AddEdge(i,i+n,1,-Ca[i]);
AddEdge(i+n,Pm,1,0);
}
AddEdge(Pm,Pt,m,0);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(Ca[i]<=Ca[j])
AddEdge(i+n,j,1,0);
int ans=Dinic();
printf("%d\n",-ans);
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问~

0%