学习笔记 - 费用流 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

学习笔记 - 费用流

发表于 更新于 分类于 Valine：

最近开始了网络流的魔鬼练习，出现了一堆脑洞题（我现在脑袋已经要变成一个杯子形了 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，欢迎提问~