一种更高效的费用流算法——zkw费用流

2018-01-12jzqjzq?

文章目录

orz原创者zkw%%%
送上zkw神犇的blog原址:传送门

费用流建立在网络最大流的基础上,一张图中最大流有且仅有一个,但是最大流条数往往不止一条,这时候对于我们来说,可能要找出这些最大流中最小(或者最大)的那一条路径(贪心策略嘛),这就是最小(最大)费用最大流
——以上就是定义嘛

我们求费用流的算法也是非常多的,目前最流行的就是Edmond-Karp经过修改过后的费用流算法了,这个我就不多说了,网上的教程也非常多

我们来分析一下EK的优缺点:EK算法的实质在于把原本的bfs换成了SPFA求得最短路从而计算最小费用,是一种沿最短路増广的算法,这样比较高效又简单地求得了答案
一个小缺点就是EK是单路増广的,这样速度也会相应地比较慢一点(不过对于费用流当今的数据范围也不会开得太大,EK问题不大)

然后zkw大神针对这个问题作出了一些改进,比如在dfs的时候可以实现多路增广,KM算法节省SPFA时间等等

zkw的原码详见上面的那个链接

然而KM算法并不会怎么办呢?其实SPFA还是可以做的,我们使用SPFA来维护每个点的距离标号,然后用zkw在dfs的思想进行多路増广,这样时间效率还是可以快很多(而且这样似乎可以跑负权图,然而zkw原版的不可以)

具体代码实现如下(Luogu3381【模板】最小费用最大流):

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
bool vis[200001];int dist[200001];
//解释一下各数组的含义:vis两个用处:spfa里的访问标记,増广时候的访问标记,dist是每个点的距离标号
int n,m,s,t,ans=0;
//s是起点,t是终点,ans是费用答案
int nedge=-1,p[200001],c[200001],cc[200001],nex[200001],head[200001];
//这里是边表,解释一下各数组的含义:p[i]表示以某一点出发的编号为i的边对应点,c表示编号为i的边的流量,cc表示编号为i的边的费用,nex和head不说了吧。。。
inline void addedge(int x,int y,int z,int zz){
p[++nedge]=y;c[nedge]=z;cc[nedge]=zz;nex[nedge]=head[x];head[x]=nedge;
}
//建边(数组模拟边表倒挂)
inline bool spfa(int s,int t){
memset(vis,0,sizeof vis);
for(int i=0;i<=n;i++)dist[i]=1e9;dist[t]=0;vis[t]=1;
//首先SPFA我们维护距离标号的时候要倒着跑,这样可以维护出到终点的最短路径
deque<int>q;q.push_back(t);
//使用了SPFA的SLF优化(SLF可以自行百度或Google)
while(!q.empty()){
int now=q.front();q.pop_front();
for(int k=head[now];k>-1;k=nex[k])if(c[k^1]&&dist[p[k]]>dist[now]-cc[k]){
//首先c[k^1]是为什么呢,因为我们要保证正流,但是SPFA是倒着跑的,所以说我们要求c[k]的对应反向边是正的,这样保证走的方向是正确的
dist[p[k]]=dist[now]-cc[k];
//因为已经是倒着的了,我们也可以很清楚明白地知道建边的时候反向边的边权是负的,所以减一下就对了(负负得正)
if(!vis[p[k]]){
vis[p[k]]=1;
if(!q.empty()&&dist[p[k]]<dist[q.front()])q.push_front(p[k]);else q.push_back(p[k]);
//SLF优化
}
}
vis[now]=0;
}
return dist[s]<1e9;
//判断起点终点是否连通
}
inline int dfs(int x,int low){
//这里就是进行増广了
if(x==t){vis[t]=1;return low;}
int used=0,a;vis[x]=1;
//这边是不是和dinic很像啊
for(int k=head[x];k>-1;k=nex[k])if(!vis[p[k]]&&c[k]&&dist[x]-cc[k]==dist[p[k]]){
//这个条件就表示这条边可以进行増广
a=dfs(p[k],min(c[k],low-used));
if(a)ans+=a*cc[k],c[k]-=a,c[k^1]+=a,used+=a;
//累加答案,加流等操作都在这了
if(used==low)break;
}
return used;
}
inline int costflow(){
int flow=0;
while(spfa(s,t)){
//判断起点终点是否连通,不连通说明满流,做完了退出
vis[t]=1;
while(vis[t]){
memset(vis,0,sizeof vis);
flow+=dfs(s,1e9);
//一直増广直到走不到为止(这样也可以省时间哦)
}
}
return flow;//这里返回的是最大流,费用的答案在ans里
}
int main()
{
memset(nex,-1,sizeof nex);memset(head,-1,sizeof head);
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int x,y,z,zz;scanf("%d%d%d%d",&x,&y,&z,&zz);
addedge(x,y,z,zz);addedge(y,x,0,-zz);
}
printf("%d ",costflow());printf("%d",ans);
return 0;
}

看完代码后的感觉是:哇和dinic好像啊

最后来说说zkw费用流的优缺点吧,原版优势在于节省了大量的跑SPFA的时间,还有多路増广的大优势,这个特点可以在许多路径都费用相同的时候派上用场, 进一步减少了重标号的时间耗费

而SPFA的多路増广版本即使多跑了SPFA,多路増广的优势犹存,所以时间上还是蛮优秀的,再加上SLF优化之后减小的常数也是很高效的

而有些时候zkw的劣势也是有的,对于流量不大, 费用不小, 增广路还较长的网络,zkw体现出来的优势并不大,甚至可能比普通EK慢。。。所以对于不同的网络zkw版本和普通EK版本各有优势,大家可自行选择