今天复习了一下网络流，复习了之前学习的使用普通SPFA不断找增广路单路增广的算法，并且学习了一下zkw网络流和折中的算法——SPFA多路增广算法，今天就让我们来一起学习一下最小(最大)费用流吧！

什么是费用流问题

在一般的最大流题目中，一般每条边只有一个参数——容量，但是费用流中每条边还多了一个参数——费用，也就是说在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以在流量最大的前提下，达到所用的费用最小或最大的要求。我们把这类问题称为最小(最大)费用最大流问题。

SPFA单路增广

我们首先讲一种最基础也是最好掌握的实现算法，就是spfa求费用流。

其实非常简单，在最大流的基础上，我们将dfs增广替换成对于费用为权值的边跑spfa得到的最短路，相当于一个贪心的思想。这个算法每次都能找到一条单位流费用和最小的路径，又由于路径中每条边的流量相等，每次增广就能使得单位流量的平均费用更小，而最大流流量是不变的，这样就能使得费用最小。不断SPFA下去找到最短的源点到汇点的路，路径上流量减去路径上的最小流量，建立反向边，进行下一次SPFA。

我们都知道网络流算法主要考建图，就算是这种简单的算法也能通过大部分费用流的题目，大部分题目还是不会卡的。

对于spfa，这里有两个小优化。

一个是slf优化，这个在之前我们的程序已经多次运用了，就是对于spfa的进队操作，进之前判一下若小于队头就直接插在队头，这个还是蛮有用的，可以提升点速度；

另一个是记路径的时候可以不用记前趋点，只要记边，反向边指向的就是前趋，就不用多开一个数组的空间。

下面贴出一份qrcer大佬的模板，感觉挺好的：

这是网络流24题中的餐巾计划问题。

题目大意是：一个饭馆每天需要使用ri条干净的餐巾，用完就脏了，干净餐巾可以由3种方式得到：

1.直接购买，p元一条；
2.快洗，需要t1天，花费w1元；
3.慢洗，需要t2天，花费w2元；

　　所以我们建6种边，把每天拆成两个点，分别为干净的（1~n）和脏的（n+1~n*2），这里要注意的是，干净的不直接向脏的连边，而是连向T，相当于必须送满ri条给顾客使用，再从S送到脏的一边。

#include<cstdio>
using namespace std;
const int inf=2147483647;
int n,m,p,t1,w1,t2,w2,tot=1,mx,q[2010],d[2010],pree[2010],h[2010];
struct edge{int to,nxt,cst,cap;}e[10010];
bool vis[2010];
int mn(int x,int y){return x>y?y:x;}
void add(int fr,int to,int cst,int cap)
{
    e[++tot]={to,h[fr],cst,cap};h[fr]=tot;
    e[++tot]={fr,h[to],-cst,0};h[to]=tot;//建一条容量为0费用为-cap的反向边且满足正反边异或值为1方便将边取反 
}
void init()
{
    scanf("%d%d%d%d%d%d",&n,&p,&t1,&w1,&t2,&w2);
    for(int i=1;i<=n;i++)
    {
        int r;scanf("%d",&r);mx+=r;
        add(0,n+i,p,inf);//直接购买花费p元 
        add(0,i,0,r);//当天用完的旧餐巾 
        add(i+n,n*2+1,0,r);//当天需要使用的新餐巾 
        if(i+t1<=n)add(i,i+n+t1,w1,inf);//快洗花费t1时间，每条w1元 
        if(i+t2<=n)add(i,i+n+t2,w2,inf);//快洗花费t2时间，每条w2元 
        if(i<n)add(i,i+1,0,inf);//不需要做任何事的餐巾积到明天（也可以先洗完然后放在那边等就是n+i连向n+i+1） 
    }
    n=n*2+1;
}
bool spfa()
{
    for(int i=1;i<=n;i++)d[i]=inf;
    int l=0,r=1;q[1]=0;vis[0]=1;
    while(l!=r)
    {
        int x=q[l=l==n?0:l+1];
        for(int i=h[x];i;i=e[i].nxt)
            if(e[i].cap&&e[i].cst+d[x]<d[e[i].to])
            {
                int v=e[i].to;
                pree[v]=i;
                d[v]=d[x]+e[i].cst;
                if(!vis[v])
                {
                    if(d[v]>d[l+1])q[r=r==n?0:r+1]=v;
                    else q[l]=v,l=l==0?n:l-1;//这边加的是slf优化，用了循环队列来写 
                    vis[v]=1;
                }
            }
        vis[x]=0;
    }
    return d[n]==inf?0:1;
}
int costflow()
{
    int cost=0,mm=0;
    while(spfa())
    {
        int mi=inf;
        for(int i=n;i;i=e[pree[i]^1].to)//记路径时记下前趋路径 
            mi=mn(mi,e[pree[i]].cap);
        for(int i=n;i;i=e[pree[i]^1].to)
        {
            int ee=pree[i];
            e[ee].cap-=mi;
            e[ee^1].cap+=mi;
        }
        cost+=d[n]*mi;
        mm+=mi;
    }
    return mm==mx?cost:0;//是否满流的判断(这道题不会出现不满流的情况，所以不加也可) 
}
int main()
{
    init();
    printf("%d",costflow());
    return 0;
}

还是非常好理解的0vo

zkw费用流

zkw费用流是基于KM算法，所以还没有学过KM算法的同学建议点击我学习一下KM算法。

和KM算法类似的，我们先对费用流算法进行分析：
我们记Di为从S出发到i的最短路
最短路算法保证, 算法结束时：
对于任意存在弧(i,j)满足Di+cij≥Dj ①
且对于每个 j 至少存在一个 i 使得等号成立 ②
算法结束后, 恰在最短路上的边满足 Dj=Di+cij

在最小费用流的计算中,我们每次总是沿 Dj=Di+cij的路径增广，增广会让流量减小，会让部分的弧变得没有流量（即暂时不存在了）
是不会破坏①，但可能会破坏②的
这可能使我们找不到每条边都满足 Dj=Di+cij 新的增广路

普通费用流的方法是：每次增广再使用 SPFA等方法重新计算D
这无疑是一种浪费

做法
Di+cij≥Dj ⇔ Di−Dj+cij≥0 ①
Di+cij=Dj ⇔ Di−Dj+cij=0 ②
对于一个顶标D，我们可以不断的dfs找Di−Dj+cij=0的增广路经

假设我们当前dfs失败
即使失败还是有一些点能满足Di−Dj+cij=0的
这些点被我们当前dfs到了
我们记这些点的点集为V

找到Δ=min{Di−Dj+cij} | i∈V,j∉V,flow ij>0
然后我们对 ∀i∈V, Dπi=Di−Δ

条件①②均没有被破坏，就可以实现类似于KM的多路增广了。

模板比较简单短小，很好理解，这里就直接给出关键部分了：

void insert(int u,int v,int w,int cost) {add(u,v,w,cost); add(v,u,0,-cost);}

int spfa()
{
    memset(mark,0,sizeof(mark));
    rep(i,0,T) d[i]=inf; 
    int l=0,r=1;
    q[l]=T;d[T]=0;mark[T]=1;
    while (l^r)
    {
        int u=q[l++]; if (l==T) l=0; mark[u]=0;
        for (int i=head[u];i;i=e[i].next)
            if (e[i^1].w && d[u]-e[i].c<d[to])
            {
                d[to]=d[u]-e[i].c;
                if (!mark[to])
                {
                    mark[to]=1;
                    q[r++]=to;
                    if (r==T) r=0;
                }
            }
    }
    return d[0]==inf? 0:1;
}

int dfs(int x,int in)
{
    if (x==T) return in;
    mark[x]=1;
    int w,used=0;
    for (int i=head[x];i;i=e[i].next)
    if (d[to]==d[x]-e[i].c && e[i].w && !mark[to])
    {
        used+=w=dfs(to,min(in-used,e[i].w));
        ans+=w*e[i].c;
        e[i].w-=w;e[i^1].w+=w;
        if(used==in) return in;
    }
    return used;
}

void zkw()
{
    while (spfa())
    {
        mark[T]=1;
        while (mark[T])
        {
            memset(mark,0,sizeof(mark));
            dfs(0,inf);
        }
    }
}

*强烈推荐的SPFA多路增广

在实际测试的过程中，我们会发现,在稠密图中，ZKW费用流有着得天独厚的优势，而在稀疏图中，ZKW费用流可能会慢的飞起，就连单路增广的SPFA速度都甚至超过了ZKW费用流，这样很容易给出题人卡你的机会。

下面我们就来介绍一下多路增广的SPFA算法，我们可以用SPFA来维护每个点的距离标号，然后用zkw在dfs的思想进行多路増广，据说这样貌似还可以跑负权图？

我们以Luogu的裸题为例子来讲解一下：

[Luogu p3381]最小费用最大流
题目描述
如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。

输入输出格式
输入格式：
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi），单位流量的费用为fi。

输出格式：
一行，包含两个整数，依次为最大流量和在最大流量情况下的最小费用。

输入输出样例
输入样例#1：
4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5
输出样例#1：
50 280
说明
时空限制：1000ms,128M

（BYX：最后两个点改成了1200ms）

数据规模：

对于30%的数据：N<=10，M<=10

对于70%的数据：N<=1000，M<=1000

对于100%的数据：N<=5000，M<=50000

这就是裸的费用流模板了，直接给出多路增广SPFA的例子，时间还是非常快的呀。

//我们使用SPFA来维护每个点的距离标号，然后用zkw在dfs的思想进行多路増广，
//这样时间效率还是可以快很多（而且这样似乎可以跑负权图，然而zkw原版的不可以） 
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

struct node
{
    int x,y,c,cc,next;
}a[2100000];//数组模拟链表存储边 
int len=1,last[210000],maxn=1e9;
int vis[210000];int dis[210000];
//解释一下各数组的含义：vis两个用处：spfa里的访问标记，増广时候的访问标记，dis是每个点的距离标号
int n,m,s,t,ans=0,x,y,c,cc,k;
//s是起点，t是终点，ans是费用答案
inline int add(int x,int y,int c,int cc)
{
    len++;
    a[len].x=x;a[len].y=y;a[len].c=c;a[len].cc=cc;
    a[len].next=last[x];last[x]=len;

    len++;
    a[len].x=y;a[len].y=x;a[len].c=0;a[len].cc=-cc;
    a[len].next=last[y];last[y]=len;

}//建边

inline bool spfa(int s,int t)//反向跑最短路，求出距离标号 
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n;i++)dis[i]=maxn;
    vis[t]=1;dis[t]=0;
    //首先SPFA我们维护距离标号的时候要倒着跑，这样可以维护出到终点的最短路径
    deque<int>p;p.push_back(t);
    //使用了SPFA的SLF优化
    while(!p.empty())
    {
        int now=p.front();p.pop_front();
        for(int k=last[now];k;k=a[k].next)
        {
            if(a[k^1].c>0)
            //首先c[k^1]是为什么呢，因为我们要保证正流，但是SPFA是倒着跑的，所以说我们要求c[k]的对应反向边是正的，这样保证走的方向是正确的
            {
                int y=a[k].y;
                if(dis[y]>dis[now]-a[k].cc)
                {
                    dis[y]=dis[now]-a[k].cc;
                    //因为已经是倒着的了，我们也可以很清楚明白地知道建边的时候反向边的边权是负的，所以减一下就对了（负负得正）
                    if(vis[y]==0)
                    {
                        vis[y]=1;
                        if(!p.empty() && dis[y]<dis[now])p.push_front(y);
                        else p.push_back(y);
                        //SLF优化
                    }
                }
            }
        } 
        vis[now]=0;//队头元素退队，设置为未访问 
    }
    if(dis[s]==maxn)return(false);
    else return(true);
    //判断起点终点是否连通
} 

int dfs(int x,int low)//这里就是进行増广了
{
    if(x==t){vis[t]=1;return low;} 
    int used=0,aa;vis[x]=1;//这边是不是和dinic很像啊
    for(int k=last[x];k; k=a[k].next)
    {
        int y=a[k].y;
        if(vis[y]==0 && a[k].c>0 && dis[x]-a[k].cc==dis[y])
        //这个条件就表示这条边可以进行増广
        {
            aa=dfs(y,min(a[k].c,low-used));
            if(aa>0)ans+=aa*a[k].cc,a[k].c-=aa,a[k^1].c+=aa,used+=aa;
            //累加答案，加流等操作都在这了
            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,maxn); 
            //一直増广直到走不到为止（这样也可以省时间哦）
        }
    }
    return(flow);;//这里返回的是最大流，费用的答案在ans里
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&x,&y,&c,&cc);
        add(x,y,c,cc);
    }
    printf("%d ",costflow());
    printf("%d",ans);
    return 0;
} 

结语

在这篇BLOG中，我们深入了解了三种费用流的解决方法，个人还是比较推荐比较稳健的SPFA多路增广。希望你喜欢这篇BLOG。