最小费用最大流

最小费用最大流(Min Cost Max Flow,MCMF,也称费用流)问题,是指在网络流图中,对于每条边在原有的基础上再增加一个限制——单位流量的费用……

一 概念

最小费用最大流(Min Cost Max Flow,MCMF,也称费用流)问题,是指在网络流图中,对于每条边在原有的基础上再增加一个限制——单位流量的费用,并且在保证流最大的情况下使得产生的费用最小。

那么在费用流问题中,一条边就可以被描述成$e=(u,v,cap,cost,flow)$,$(u,v)$是边的起点和终点,$cap$是容量限制,$cost$是单位流量所产生的费用,$flow$是当前流量。
之所以强调“单位流量“,是因为这条边总产生的费用为$flow\times cost$。

网络的最大流显然是一定的,但是最小割可能会有多个。每个割的单位流量费用不同,于是才有了费用流问题。注意:费用流是在保证流最大的前提下,使得总产生的费用最小。


二 解决

1 思路

网络的最大流可能是由多条增广路径共同组成。如下图,增广路$s \to 1 \to 4 \to t$和$s \to 2 \to 3 \to t$共同组成了网络的最大流。

mcmf1

那么先分析一条增广路的费用。
设该费用为$p$,该增广路经过边$e_1,e_2,…,e_m$,每条边的单位流量费用分别是$c_1,c_2,…,c_m$,且该路上当前流量为$a$,那么可以得出下面的式子:

$$ p = ac_1 + ac_2 + … + ac_m = a(c_1+c_2+…+c_m) $$
也就是:
$$ p = a \times \sum\limits_{i=1}^m c_i $$

如果能保证$p$最小且该增广路在最大流中,那么$a$一定是个定值,且等于路上的最小割。
要保证$p$最小,就是要让后面的$\sum$最小,它表示该增广路上各条边的单位费用之和。

那么我们能想到什么?最短路
把$cost$这一元看作边的边权,那么这个$\sum\limits_{i=1}^m c_i$就表示路上的边权之和。我们要求出最小的$\sum$,就是在求图上的最短路。

那么就有了贪心的思路:每次找出图上$s\to t$的最短路并把它增广,那么这条路就“断”了,然后再找最短路,直到无法增广,此时网络达到最大流,且产生的费用最小。

2 代码

利用spfa找最短路,每次进行单路增广,并模拟dinic中dfs增广的退栈过程来实现数据的更新(这需要记录搜索时进入每个节点的边时哪一条边)。

注意,因为反向边是反悔机制,用来抵消正向边的影响,所以反向边的单位流量费用应该是对应正向边的相反数。

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
const int CP=5e3+3;
const int CE=1e5+1e2;

const int INF=0x3f3f3f2f;

//快读
int read(){
int s=0,ne=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
for(;c>='0'&&c<='9';c=getchar()) s=((s<<1)+(s<<3))+c-'0';
return s*ne;
}

//边表
class fs{
public:
int from,to,nxt,cap,cost,flow;
void init(int r,int t,int n,int c,int s,int f)
{from=r; to=t; nxt=n; cap=c; cost=s; flow=f;}
}E[CE];
int hd[CP],ecnt=1;
void _add(int x,int y,int c,int s){
E[++ecnt].init(x,y,hd[x],c,s,0);
hd[x]=ecnt;
}
void add(int x,int y,int c,int s){
_add(x,y,c,s);
_add(y,x,0,-s); //反向边
}

//v define
int n,m,s,t;

//mcmf
int mincost=0,maxflow=0;
int dist[CP]; //dist : 单源最短路
bool ins[CP]; //ins[i] : i 是否在队列内
int prv[CP]; //prv[i] : 当前最短路中进入点 i 的边
int rst[CP]; //rst[i] : s->i路上的最小割

bool Augment(int _s,int _t) //spfa
{
memset(ins,false,sizeof(ins));
memset(dist,0x3f,sizeof(dist));
memset(rst,0x3f,sizeof(rst));

queue<int>Q;
Q.push(_s); dist[_s]=0; ins[_s]=true;

while(!Q.empty())
{
int u=Q.front(); Q.pop();
ins[u] = false;
for(int k=hd[u]; k; k=E[k].nxt){
fs e=E[k];
if(e.cap-e.flow > 0 && dist[e.to] > dist[u]+e.cost)
{
dist[e.to] = dist[u]+e.cost; //松弛,边权为cost
prv[e.to] = k; //记录入边
rst[e.to] = min(rst[u], e.cap-e.flow); //递推
if(!ins[e.to]){
Q.push(e.to); ins[e.to] = true;
}
}
}
}

return dist[_t]<INF; //没到达 _t ,则dist[_t]=INF
}
void update(int _s,int _t){ //更新(模拟退栈)
int pos=_t; //从终点开始
while(pos != _s){ //直到起点
E[prv[pos]].flow += rst[_t]; //正向
E[prv[pos]^1].flow -= rst[_t]; //反向
pos = E[prv[pos]].from; //前往上一个节点
}
}
void mcmf(int _s,int _t){ //主调用函数
while(Augment(_s,_t)){
maxflow += rst[_t];
mincost += dist[_t]*rst[_t]; //单位费用 * 流量
update(_s,_t); //更新
}
}


三 网络流建模

1 点容量问题

拆点建模一般应用在点存在容量限制的网络流问题中,因此也可以用来求解图上的最小割点集(此时点的容量均为$1$,详见「题解」奶牛的电信)。

把图上的每个非源非汇点$i$拆成$i,i+n$两个点($n$是总点数),其中点$i$连接原图中该点的入边,点$i+n$连接原图中该点的出边,这样$i\to i+n$这条边就能代表原图中的点$i$,对这条边设置容量限制,实际就是对该点设置容量限制。

如下图:

mcmf2

2 点权均衡问题

原题:负载平衡问题

给定一张由$n$个点组成的环,每个点$i$有一个点权$x_i$,点权可以在相邻节点间转移。记$ \overline x = \sum\limits_{i=1}^n x_i \div n$,求最少的转移量,使得每个$x_i$都等于$\overline x$。

可以把仓库分成两类:

  1. $x_i > \overline x$ 的仓库$i$,记为图$L$。
  2. $x_i < \overline x$ 的仓库$i$,记为图$R$。

$x_i = \overline x$的仓库不会影响答案,所以放在哪一类里面都行。

很明显,$L$中节点的点权需要转移到$R$中节点去。
把这个点权变成边权,那么新建总源$s$和总汇$t$,连边$s\to L$,$L \rightleftarrows R$与$R\to t$。具体方法如下:

  1. $s\to L$边上的流量限制为$L$中节点点权超出$\overline x$的部分,即$x_i - \overline x$,转移费用为$0$。
  2. $R\to t$边上的流量限制为$R$中节点点权不足$\overline x$的部分,即$\overline x- x_i$,转移费用为$0$。
  3. 图上所有相邻节点互相连双向边,边上没有流量限制,因为可以无限转移。不过转移的费用就是$1$。

这样,当增广一条路时,$s\to L$的边流量增大,使得$L$中节点点权变小;$R\to t$的边流量也增大,使得$R$中节点点权变大。
其实上意味着$L,R$中点的点权会更接近于平均值$\overline x$。当网络流达到最大时,也就是说所有不等于平均值的点权都已经被增广到平均值大小,也就达到了负载平衡。

那么跑费用流,输出最小费用。


四 二分图匹配问题

1 最大基数匹配

二分图的不带权最大匹配问题也称最大基数匹配问题。基础部分详见:二分图基础

新建总源$s$,总汇$t$。设二分图的左图为$L$,右图为$R$,则将$s$向$L$中的所有节点连边,$R$中的所有节点向$t$连边,并将二分图中原有的无向边转化成$L\to R$的有向边。所有边的容量均为$1$。
于是我们可以得到一张网络流图,如下:

mcmf3

边的容量为$1$保证了同一条边不会同时在多条增广路中,那么任意两条增广路的交点只会是$s$和$t$。此时若求出最大流,那么最大流就是该图的最大匹配,$L\to R$中流量为$1$的边就是最大匹配中的匹配边。

代码参见飞行员配对问题

2 最大带权匹配

若存在一种匹配方案,使得图上所有点都被匹配,则称这个匹配为二分图的完美匹配。

先考虑存在完美匹配时的情况。

依然是上面的建图思路,并把边权看作费用,$s\to L$和$R\to t$的边费用为$0$。那么显然可以求出最小费用最大流。

把最大边权和转化成最小费用?两种思路:每次延着最长路增广 和 使费用为边权的相反数。

但是此时最小费用其实受最大流的限制,也就是说仅当流最大时才保证费用最小,那么这样求出来的最小费用实际上是完美匹配的最小边权和。为什么呢?当存在完美匹配时,最大流一定是这个完美匹配,那么这时候最小费用才对应着图上的最小边权和,那么也就是完美匹配的最小边权和。

那么怎样求不受边数限制的最大带权匹配?

也就是说要摆脱这个“最大流”的限制。怎么做呢?
每次增广后都记录一下当前的总费用,直到当前流最大,那么所有可能的匹配的边权和我们都已经求出来了,只要把最小(如果费用是边权的相反数)的那个挑出来就好了。

建图的图解如下:

mcmf4

3 最大带权独立集

选出一些节点,使得这些节点都没有边相连,称其为原图的一个独立集。

那么最大带权独立集就是在点有点权的基础上,求出一个点权和最大的独立集。

还是上面的思路。
新建总源$s$,总汇$t$。设二分图的左图为$L$,右图为$R$。将$s$向$L$中的所有节点连边,容量为$L$中节点的点权;$R$中的所有节点向$t$连边,容量为$R$中节点的点权。并将二分图中原有的无向边转化成$L\to R$的有向边,容量无限。

那么有: 最大独立集 = 总点权-最小割(最大流)

割中的边一定是$s\to L$或$R\to t$的边。增广它们等于删掉这些边,相当于删掉$L,R$中的结点。删掉最小割一定会导致图不连通。而在原二分图中,删掉割中的节点及所连接的边,就会导致图上一条边也没有!
那么剩下的节点肯定是独立集。又保证了割最小,所以求得了最大独立集。

图解:

mcmf5

作者

ce-amtic

发布于

2019-03-19

更新于

2021-01-04

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×