最小费用最大流
费用流就是在最大流的基础上给每条边加上了费用，求最大流的前提下使得总费用最小。
主要有两种算法：
- mcmf算法—spfa单路增广
- zkw费用流—spfa多路增广，和dinic最大流算法类似
两种算法实现步骤
-
mcmf
- 使用spfa求得源点到汇点的最短路，并记录最短路径上每个点的前驱
- 根据记录的前驱，从汇点沿着前驱返回源点，对经过的边减去这个最短路径流过的流量，反向边加上相应的流量
- 重复1、2，直到源点和汇点不连通
-
zkw
- 每次使用最短路算法spfa，判断源点和汇点是否连通，并且实现Dinic算法中的分层效果（至于这里为什么要反向跑最短路，我也不是很清楚）
- 如果最短路得到源点和汇点连通，接下来进行多次dfs流量增广，这里和Dinic算法基本一样（dfs增广和Dinic中的dfs增广是一样的）
- 重复1、2，直到源点和汇点不连通
两种算法的直观证明：每次最短路的结果都是从源点到汇点的最小费用，减去这条最小费用路径上的流过的的流量，重复直到源点和汇点不连通，此时达到最大流量，由于每次费用都是当前图中的最小费用，最后的费用自然就是最小费用。
效率分析
实践中，zkw效率非常奇怪，. 在某一些图上, 算法速度非常快, 另一些图上却比纯 SPFA 增广的算法慢. 不少同学经过实测总结的结果是稠密图上比较快, 稀疏图上比较慢, 但也不尽然。
zkw从理论上分析得出：对于最终流量较大, 而费用取值范围不大的图, 或者是增广路径比较短的图 (如二分图), zkw 算法都会比较快. 原因是充分发挥优势. 比如流多说明可以同一费用反复增广, 费用窄说明不用改太多距离标号就会有新增广路, 增广路径短可以显著改善最坏情况, 因为即使每次就只增加一条边也可以很快凑成最短路. 如果恰恰相反, 流量不大, 费用不小, 增广路还较长, 就不适合 zkw 算法了.
hzwer表示zkw不容易被卡，建议都使用zkw算法。如果卡spfa或者你是“关于 SPFA，它死了”言论的追随者，可以使用 Primal-Dual 原始对偶算法将 SPFA 改成 Dijkstra！
代码模板
zkw算法
给出点个数，有向边个数，源点序号，汇点序号。给出边的起点、终点、最大流量、单位流向的费用。
求最大流情况下的最小费用。
4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5
50 280
//链式前向星存储
#include <cstdio>
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
const int N=5e3+5,M=1e5+5;
struct node{
int from,to,flow,cost,next;
}e[M];
int h[N],idx;
int inf=0x3f3f3f3f;
bool vis[N];
//vis两个用处：spfa里的访问标记，増广时候的访问标记
int dis[N];
//dis是spfa最短路的距离数组
int n,m,s,t,ans;//ans是费用答案
inline void add(int from,int to,int flow,int cost){
e[idx].from=from,e[idx].to=to,e[idx].flow=flow,e[idx].cost=cost,e[idx].next=h[from],h[from]=idx++;
}
inline void insert(int from,int to,int flow,int cost){
add(from,to,flow,cost),add(to,from,0,-cost);
}
int q[N];
inline bool spfa(int s,int t){//反向跑最短路，求出距离标号
memset(vis,0,sizeof(vis));//这里的vis相当于inq，标记是否在队列中
memset(dis,0x3f,sizeof(dis));
//首先SPFA我们维护距离标号的时候要倒着跑，这样可以维护出到终点的最短路径
int hh=0,tt=0;
q[tt++]=t;
vis[t]=true,dis[t]=0;
//使用了SPFA的SLF优化
while(hh!=tt){
// int now=p.front();p.pop_front();
int now=q[hh++];if(hh==N+1)hh=0;
for(int i=h[now],y;~i;i=e[i].next){
if(e[i^1].flow>0){
//首先c[k^1]是为什么呢，因为我们要保证正流，但是SPFA是倒着跑的，所以说我们要求c[k]的对应反向边是正的，这样保证走的方向是正确的
y=e[i].to;
if(dis[now]-e[i].cost<dis[y]){
//因为已经是倒着的了，我们也可以很清楚明白地知道建边的时候反向边的边权是负的，所以减一下就对了（负负得正）
dis[y]=dis[now]-e[i].cost;
if(!vis[y]){
vis[y]=true;
//slf优化
if(hh!=tt&&dis[y]<dis[now]){
--hh;
if(hh<0)hh=N;
q[hh]=y;
}
else {
q[tt++]=y;
if(tt==N+1)tt=0;
}
}
}
}
}
vis[now]=false;
}
//判断起点和终点是否连通
if(dis[s]==inf) return false;
else return true;
}
inline int dfs(int x,int nowflow){//这里是进行增广
if(x==t){vis[t]=true;return nowflow;}
int totflow=0;vis[x]=true;
//totflow表示从这个点总共可以增广多少流量
for(int i=h[x];~i;i=e[i].next){
int y=e[i].to;
if(!vis[y]&&e[i].flow>0&&dis[x]==dis[y]+e[i].cost){
//这里dis[x]==dis[y]+e[i].cost相当于确定x是由y更新过来的，作用相当于dinic算法中的层次，表示x是y的下一层
int canflow=dfs(y,min(e[i].flow,nowflow));
//canflow表示从这条边最多增广的流量
if(canflow){
ans+=canflow*e[i].cost;//流量*单位费用
e[i].flow-=canflow,e[i^1].flow+=canflow;
totflow+=canflow;
nowflow-=canflow;
}
if(nowflow<=0)break;
}
}
return totflow;
}
inline int costFlow(){
int flow=0;
while(spfa(s,t)){//判断起点终点是否连通，不连通说明满流，做完了退出
vis[t]=true;
// cout<<cnt<<"--------"<<endl;
while(vis[t]){
memset(vis,0,sizeof(vis));
flow+=dfs(s,inf);
// cout<<cnt<<endl;
}
}
return flow;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
memset(h,-1,sizeof(h));
for(int i=0,from,to,flow,cost;i<m;i++){
scanf("%d%d%d%d",&from,&to,&flow,&cost);
insert(from,to,flow,cost);
}
int flow=costFlow();
printf("%d %d",flow,ans);
// cout<<ans<<endl;
return 0;
}
/*
4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5
50 280
*/
mcmf算法
题目描述 Description
一个餐厅在相继的 N 天里，每天需用的餐巾数不尽相同。假设第 i 天需要 ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为 p 分；或者把旧餐巾送到快洗部，洗一块需 m 天，其费用为 f 分；或者送到慢洗部，洗一块需 n 天(n>m)，其费用为 s<f 分。
每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 N 天中餐巾使用计划，使总的花费最小。
编程找出一个最佳餐巾使用计划.
输入描述 Input Description
第 1 行有 6 个正整数 N,p,m,f,n,s。N 是要安排餐巾使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗一块餐巾需要的费用；n 是慢洗部洗一块餐巾需用天数；s 是慢洗部洗一块餐巾需要的费用。接下来的 N 行是餐厅在相继的 N 天里，每天需用的餐巾数。
输出描述 Output Description
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
样例输入 Sample Input
3 10 2 3 3 2
5
6
7
样例输出 Sample Output
145
题解
这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。
经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi->Xi+1），不需要花费，送到快洗部(Xi->Yi+m)，费用为f，送到慢洗部(Xi->Yi+n)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S->Yi)，费用为p。
#include<iostream>
#include<cstdio>
#define inf 0x7fffffff
#define T 2001
using namespace std;
int cnt=1,day,p,m,f,n,s,ans;
int from[2005],q[2005],dis[2005],head[2005];
bool inq[2005];
struct data{int from,to,next,v,c;}e[1000001];//v 流，c 费用
void ins(int u,int v,int w,int c)
{
cnt++;
e[cnt].from=u;e[cnt].to=v;
e[cnt].v=w;e[cnt].c=c;
e[cnt].next=head[u];head[u]=cnt;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);}
bool spfa()
{
for(int i=0;i<=T;i++)dis[i]=inf;
int t=0,w=1,i,now;
dis[0]=q[0]=0;inq[0]=1;
while(t!=w)//队列，宽搜
{
now=q[t];t++;if(t==2001)t=0;
for(int i=head[now];i;i=e[i].next)
{
if(e[i].v&&dis[e[i].to]>dis[now]+e[i].c)
{
from[e[i].to]=i;
dis[e[i].to]=dis[now]+e[i].c;
if(!inq[e[i].to])
{
inq[e[i].to]=1;
q[w++]=e[i].to;
if(w==2001)w=0;
}
}
}
inq[now]=0;
}
if(dis[T]==inf)return 0;return 1;
}
void mcf()
{
//x记录这条最短路（源点到汇点的最小费用，求最短路过程中，点之间的边权用费用代替）上的最小容量
int i,x=inf;
i=from[T];
while(i)
{
x=min(e[i].v,x);
i=from[e[i].from];
}
//x为这条增光路上的最小容量
//根据记录的前驱，从汇点沿着前驱返回源点，对经过的边减去这个最短路径流过的流量，反向边加上相应的流量
i=from[T];
while(i)
{
e[i].v-=x;
e[i^1].v+=x;
ans+=x*e[i].c;
i=from[e[i].from];
}
}
int main()
{
scanf("%d%d%d%d%d%d",&day,&p,&m,&f,&n,&s);
for(int i=1;i<=day;i++)
{
if(i+1<=day)insert(i,i+1,inf,0);//起点，终点，容量，费用
if(i+m<=day)insert(i,day+i+m,inf,f);
if(i+n<=day)insert(i,day+i+n,inf,s);
insert(0,day+i,inf,p);
}
int x;
for(int i=1;i<=day;i++)
{
scanf("%d",&x);
insert(0,i,x,0);
insert(day+i,T,x,0);
}
while(spfa())mcf();
printf("%d",ans);
return 0;
}