最小费用最大流——EK & zkw费用流

VenusM1nT · 2018-11-26 19:00:31 · 个人记录

来糊一篇博客……顺便可以记记模板啥的……

废话不多说直接进入正题……

Edmonds-Karp

前置芝士：Spfa

核心思想算是贪心吧……

每次跑一遍Spfa，以边的费用跑一遍最短路，这样可以确保找到一条费用最小的路径，然后在跑的过程中计算出流量并记录路径，然后把路径上的边的流量都减掉就行了

模板如下（使用链式前向星存图）

变量解释：dis为最短距离，f为最大流，fr为路径，flow为边费用，w为边流量

bool Spfa()//以费用为长度跑最短路
{
    memset(dis,60,sizeof(dis));
    memset(inq,0,sizeof(inq));
    q.push(S);
    dis[S]=0;
    inq[S]=1;
    f[S]=inf;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=fst[u];i;i=nxt[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]+flow[i] && w[i])
            {
                dis[v]=dis[u]+flow[i];
                f[v]=min(f[u],w[i]);//记录最大流
                fr[v]=i;//记录路径
                if(!inq[v])
                {
                    q.push(v);
                    inq[v]=1;
                }
            }
        }
    }
    return dis[T]!=inf;
}
void ModifyFlow()//跑完之后处理路径
{
    int u=T;
    while(u!=S)
    {
        int id=fr[u];
        w[id]-=f[T];
        w[id^1]+=f[T];//网络流常用操作
        u=to[id^1];
    }
    ans+=f[T]*dis[T];
}
void MCMF()
{
    while(Spfa()) ModifyFlow();//跑到无法到达汇点为止
}

zkw费用流

前置芝士：Spfa（最好是SLF_Spfa），Dinic

个人感觉zkw大爷的这个方法和Dinic很相似啊……

先%%%zkw大爷

然后开始讲（瞎）吧（BB）

先从汇点跑Spfa，预处理出到每个位置的最短距离（这里用了SLF优化），然后跑Dinic找增广路，跑最大流，用最大流乘上距离，一直跑直到满流即可

（Dinic还能加弧优化！）

至于为什么这个方法快……我一时半会儿也想不到……

总之%%%zkw大爷肯定没错辣

模板如下（使用链式前向星存图，变量命名规则与上方一致）

bool Spfa()//SLF_Spfa
{
    memset(dis,60,sizeof(dis));
    memset(inq,0,sizeof(dis));
    q.push_front(T);
    dis[T]=0;
    inq[T]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        inq[u]=0;
        for(int i=fst[u];i;i=nxt[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]-flow[i] && w[i^1])//因为是反过来跑的，所以费用是减，w数组的下标也要^1
            {
                dis[v]=dis[u]-flow[i];
                if(!inq[v])
                {
                    if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    inq[v]=1;
                }
            }
        }
    }
    return dis[S]!=inf;
}
int Dfs(int u,int stream)//弧优化Dinic【伪】
{
    vis[u]=1;
    if(u==T || !stream) return stream;
    int used=0;
    for(int i=cur[u];i;i=nxt[i])
    {
        cur[u]=i;
        int v=to[i];
        if(dis[v]==dis[u]-flow[i] && w[i] && !vis[v])
        {
            int fl=Dfs(v,min(stream,w[i]));
            if(fl)
            {
                used+=fl;
                stream-=fl;
                w[i]-=fl;
                w[i^1]+=fl;
                if(!stream) break;
            }
        }
    }
    return used;
}
void zkwMCMF()
{
    while(Spfa())
    {
        vis[T]=1;
        while(vis[T])//一直跑到满流
        {
            memcpy(cur,fst,sizeof(fst));
            memset(vis,0,sizeof(vis));
            ans+=dis[S]*Dfs(S,inf);
        }
    }
}

扩展：最大费用最大流

做法有两种……

做法一：从建图下手

最小费用最大流的建图是这样：

    AddEdge(from,to,flow,cost);
    AddEdge(to,from,0,-cost);

那我们就采用一种求最长路时会用的技巧，把费用变负，再直接跑即可

建图如下：

    AddEdge(from,to,flow,-cost);
    AddEdge(to,from,0,cost);

做法二：从函数下手

我们还可以使用另一种求最长路时的技巧，即改变Spfa的松弛条件

（inf的值也要随之改变）