最小费用最大流

网络流是OI中比较常出现的算法，而最小费用最大流是其最常用的算法之一，阅读本文前，请确保掌握了网络最大流的Dinic的求法，详见网络最大流

前言

本文发表于：

• 个人博客：链接
• 洛谷博客：链接

网络流是OI中比较常出现的算法，而最小费用最大流是其最常用的算法之一，阅读本文前，请确保掌握了网络最大流的Dinic的求法，详见网络最大流

最小费用最大流算法

简介

最小费用最大流（以下简称费用流），是在网络最大流的基础上，给每个边增加了另一个值——费用，代表每流过一个单位的流量，就会耗费这些费用。而费用流算法，就是在求最大流的同时，找出所花费用最小的方案，并求出这个最小费用。

实现方法

首先，对于同一个图，它的最大流是一个固定的值，但是有很多方案，而求费用最小的走法，便可以利用最短路算法，以费用为最短路的边权。

思考一下，Dinic中的反边思想实际上是让程序可以沿着反边跑回去，达到反悔目的。所以费用流中，反边的费用需要设置成正边的相反数，保证在返回时费用也会还回来。

由于反边有负边权，所以要用已死的SPFA

把$Dinic$中的$Bfs$改为$SPFA$即可,每次找残量图中$S-T$的最短路径（费用作为边权），并按照$Dinic$的方式增广这条路径。

$Dinic$增广时需要把残量图中流量更改，所以要用能记录路径的$SPFA$

建图

int head[N],to[N],next[N],f[N],c[N];//f是容量，c是费用
int cnt=1;
void Add(int x,int y,int z,int cost)
{
    to[++cnt]=y;
    f[cnt]=z;
    c[cnt]=cost;
    next[cnt]=head[x];
    head[x]=cnt;
}

SPFA

int dis[N];/*spfa的距离数组*/
int flow[N];/*源点到此处流量*/
int vis[N];
int pre[N];//每个点的前驱 
int last[N];
bool Spfa() 
{
	memset(dis,0x7f,sizeof(dis));
	memset(flow,0x7f,sizeof(flow));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(S);
	vis[S]=1,dis[S]=0;
	pre[T]=-1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=next[i])
		{
			int v=to[i];
			if(f[i]>0 && dis[v]>dis[u]+c[i])//有残量，能松弛
			{
				dis[v]=dis[u]+c[i];//更新距离
				pre[v]=u;//SPFA记录前驱
				last[v]=i;//记录边的编号，便于增广时更改边权 
				flow[v]=min(flow[u],f[i]);
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return ~pre[T];
}

主函数

int Flow,Cost;
void Mcmf()
{
	while(Spfa())
	{
		int u=T;
		Flow+=flow[T];
		Cost+=flow[T]*dis[T];
		while(u!=S)//遍历这次的增广路（最短路） 
		{
			f[last[u]]-=flow[T];//更新边权 
			f[last[u]^1]+=flow[T];
			u=pre[u];
		}
	}
}

总结

这种费用流算法实际上就是在增广时优先考虑费用（用最短路$\text{SPFA}$实现），保证费用最小（反正由于反边的存在，$\text{Dinic}$怎么流到最后都能流出最大流 ）。

完整代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define next adjagag
using namespace std; 
const int N=1000010;

int head[N],to[N],next[N],f[N],c[N];
int cnt=1;
int n,m,S,T;
void Add(int x,int y,int z,int cost)
{
    to[++cnt]=y;
    f[cnt]=z;
    c[cnt]=cost;
    next[cnt]=head[x];
    head[x]=cnt;
}

int dis[N];
int flow[N];
int vis[N];
int pre[N];
int last[N];
bool Spfa() 
{
	memset(dis,0x7f,sizeof(dis));
	memset(flow,0x7f,sizeof(flow));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(S);
	vis[S]=1,dis[S]=0;
	pre[T]=-1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=next[i])
		{
			int v=to[i];
			if(f[i]>0 && dis[v]>dis[u]+c[i])
			{
				dis[v]=dis[u]+c[i];
				pre[v]=u;
				last[v]=i;
				flow[v]=min(flow[u],f[i]);
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return ~pre[T];
}

int Flow,Cost;
void Mcmf()
{
	while(Spfa())
	{
		int u=T;
		Flow+=flow[T];
		Cost+=flow[T]*dis[T];
		while(u!=S)
		{
			f[last[u]]-=flow[T];
			f[last[u]^1]+=flow[T];
			u=pre[u];
		}
	}
}

int main()
{
    scanf("%d %d %d %d",&n,&m,&S,&T);
    for(int i=1;i<=m;i++)
    {
        int x,y,z,c;
        scanf("%d %d %d %d",&x,&y,&z,&c);
        Add(x,y,z,c);
        Add(y,x,0,-c);
    }
    Mcmf();
    printf("%d %d\n",Flow,Cost);
    return 0;
}