最近做了一道费用流，但是需要更高效的费用流
这就引出了ZKW发明的网络流
ZKW的blog上讲的很清楚，这里我再复制一点
简单介绍
我们在普通的费用流中，使用了spfa求最短路
根据最短路的性质有
(1) 对任一条边(u,v)都有dis[u]<=dis[v]+w(u,v)
(2) 最短路上的边(u,v)必有dis[u]=dis[v]+w(u,v)
会发现上面那个不等式，有点类似KM算法中对于顶标的定义：
可行顶标是一个结点函数l，对于任意一条边（x，y）都有l(x)+l(y)>=w(x,y)
这就提醒我们可以像KM算法一样设置一个“顶标”
增广的时候，只有当边(u,v)满足dis[v]+w(u,v)=dis[u]才去从源点增广
如果发现增广不到汇点，则修改dis值.
修改dis值，即是将所有在增广路上的点u的dis加上一个delt，
而delt=min(dis[v]+w(u,v)-dis[u]) ，其中u在增广路上，v不在
和KM 一样，这样至少会多使一条边满足(2)可增广，且不会破坏(1).
这个delt可以和KM里面一样，在增广的时候顺便求. 复杂度降成 O(|V|)
其做法本质是看到了SPFA做最短路时，做了很多无用功，
即也会去更新绕很远实质不可能被用到的一些顶点.
ZKW算法，就利用最短路上必有dis[v]+w(u,v)=dis[u] 的特点少去尝试了很多无用的顶点.
“zkw” 费用流算法在哪些图上慢
和 SPFA 直接算法相比, 由于同属于沿最短路增广的算法, 实际进行的增流操作并没有太多的区别, 每次的增流路径也大同小异. 因此不考虑多路增广时, 增广次数应该基本相同. 运行时间上主要的差异应当在于如何寻找增流路径的部分.
那么 zkw 算法的优势在于哪里呢?
与 SPFA 相比, KM 的重标号方式明显在速度上占优, 每次只是一个对边的扫描操作而已. 而 SPFA 需要维护较为复杂的标号和队列操作, 同时为了修正标号, 需要不止一次地访问某些节点, 速度会慢不少. 另外, 在 zkw 算法中, 增广是多路进行的, 同时可能在一次重标号后进行多次增广. 这个特点可以在许多路径都费用相同的时候派上用场, 进一步减少了重标号的时间耗费.
对于最终流量较大, 而费用取值范围不大的图, 或者是增广路径比较短的图 (如二分图), zkw 算法都会比较快. 原因是充分发挥优势. 比如流多说明可以同一费用反复增广, 费用窄说明不用改太多距离标号就会有新增广路, 增广路径短可以显著改善最坏情况, 因为即使每次就只增加一条边也可以很快凑成最短路.
如果恰恰相反, 流量不大, 费用不小, 增广路还较长, 就不适合 zkw 算法了.
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=5001;
const int INF=1e9;
int tot=-1,st[N],pre[N],dis[N],n,m,ans=0,s,t,cost=0;
struct node{
int x,y,v,c,nxt;
};
node way[N*10];
bool vis[N];
void add(int u,int w,int z,int cc)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].c=cc;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].v=0;way[tot].c=-cc;way[tot].nxt=st[w];st[w]=tot;
}
int solve(int now,int flow)
{
vis[now]=1;
if (now==t)
{
cost+=-dis[now]*flow;
ans+=flow;
return flow;
}
int delta;
for (int i=st[now];i!=-1;i=way[i].nxt)
{
if (way[i].v&&!vis[way[i].y]&&dis[way[i].y]==dis[now]+way[i].c)
{
delta=solve(way[i].y,min(flow,way[i].v));
if (delta)
{
way[i].v-=flow;
way[i^1].v+=flow;
return delta;
}
}
}
return 0;
}
int reget()
{
if (vis[t]) return 1;
int mn=INF;
for (int i=0;i<=tot;i++)
{
if (way[i].v&&vis[way[i].x]&& !vis[way[i].y])
mn=min(mn,dis[way[i].x]+way[i].c-dis[way[i].y]);
}
if (mn==INF) return 0;
for (int i=1;i<=n;i++)
if (vis[i]) dis[i]-=mn;
return 1;
}
void zkw()
{
do
{
memset(vis,0,sizeof(vis));
solve(s,INF);
}
while (reget());
printf("%d %d",ans,cost);
}
int main()
{
memset(st,-1,sizeof(st));
scanf("%d%d",&n,&m);
scanf("%d%d",&s,&t);
int u,w,z,cc;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&u,&w,&z,&cc);
add(u,w,z,cc);
}
zkw();
}