ZKW网络流（从入门到出门）

ZKW大神的blog链接

最近做了一道费用流，但是需要更高效的费用流

这就引出了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=;
const int INF=;
int tot=-,st[N],pre[N],dis[N],n,m,ans=,s,t,cost=;
struct node{
    int x,y,v,c,nxt;
};
node way[N*];
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=;way[tot].c=-cc;way[tot].nxt=st[w];st[w]=tot;

}

int solve(int now,int flow)
{
    vis[now]=;
    if (now==t)
    {
        cost+=-dis[now]*flow;
        ans+=flow;
        return flow;
    }
    int delta;
    for (int i=st[now];i!=-;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^].v+=flow;
                return delta;
            }
        }
    }
    return ;
}

int reget()
{
    if (vis[t]) return ;
    int mn=INF;
    for (int i=;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 ;
    for (int i=;i<=n;i++)
        if (vis[i]) dis[i]-=mn;
    return ;
}

void zkw()
{
    do
    {
        memset(vis,,sizeof(vis));
        solve(s,INF);
    }
    while (reget());
    printf("%d %d",ans,cost);
}

int main()
{
    memset(st,-,sizeof(st));
    scanf("%d%d",&n,&m);
    scanf("%d%d",&s,&t);
    int u,w,z,cc;
    for (int i=;i<=m;i++)
    {
        scanf("%d%d%d%d",&u,&w,&z,&cc);
        add(u,w,z,cc);
    }
    zkw();
}