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();
}