图论-zkw费用流
这是一个求最小费用最大流的算法，因为发明者是神仙zkw，所以叫zkw费用流（就是zkw线段树那个zkw）。有些时候比EK快，有些时候慢一些，没有比普通费用流算法更难，所以学zkw费用流之前，不需要先掌握普通费用流。
前置知识：\(\texttt{网络最大流}\)。
在学了网络最大流后，如果在没条边上加个限制，就是 \(cost\)，表示这条边上每走过 \(1\) 流量就要付费 \(cost\)，求在最大流的情况下，要交的最少费用。
如上费用流图，最大流为 \(1\)，在达到最大流的同时，最小费用为 \(3\)。最小费用路径：\(s\to1\to2\to t\)，\(1\times (2+0+1)=3\)。
像这种图，普通费用流算法更快，因为它一次只增广一条路径。但一些大的费用流图往往最大流要经过好多路径，那么zkw费用流快得多。那么为什么还要有EK的存在呢？因为有些毒瘤题专门卡zkw费用流（路径长，最大流路径单一）。
接下来开始讲zkw费用流的实现。 首先凡是网络流题，都是要建双向边的，要不然就“走不了回头路”了。对于费用流，走回头路可以把钱要回来，所以建边如下：
class Graph{
public:
int top,to[M<<1],fw[M<<1],ct[M<<1];
//top表示边数，因为后面要把互为反边的边通过^1获得，所以正边的编号要为偶数，然后负边的编号要为正边+1
//to表示这条边通往的节点，fw表示边的流量，ct表示边的费用
vector<int> g[V];//比较奇怪的建边方式
Graph(){top=1;}
void add(int x,int y,int f,int c){
g[x].push_back(++top);
to[top]=y,fw[top]=f,ct[top]=c;
}
void Add(int x,int y,int f,int c){
add(x,y,f,c),add(y,x,0,-c);
//如同最大流，建反边，钱可以走反边要回来，所以反边费用为-c
}
};
然后开始做最小费用最大流。先看看求出答案的框架：
void mcmf(){
while(spfa()){
vis[t]=1;
while(vis[t]){
for(int i=1;i<=p;i++) vis[i]=0;
fans+=dfs(s,inf);
}
}
}
//fans表示最大流，cans表示最小费用，在dfs中求
然后来看这个 \(\texttt{spfa()}\) 他复活了，以边的费用为边权，从 \(t\) 到 \(s\) 反向跑最短路。这个 \(\texttt{spfa()}\) 有 \(3\) 个作用：
1.把图的点层次分出来，使增广有秩序。
2.把图的最短路跑出来，保证最小费用。
3.把图的连通性算出来，以便抉择增广。
我也不知道为什么作用这么整齐，代码：
bool spfa(){
//vis维护spfa，dep表示连通性+点层次+最短路
for(int i=1;i<=p;i++) vis[i]=0,dep[i]=inf;
q.push_back(t),vis[t]=1,dep[t]=0;
while(q.size()){
int x=q.front();q.pop_front(),vis[x]=0;
for(auto i:g[x])if(fw[i^1]&&dep[to[i]]>dep[x]-ct[i]){
dep[to[i]]=dep[x]-ct[i]; //dep表示最短路
if(!vis[to[i]]){
vis[to[i]]=1;
if(q.size()&&dep[to[i]]<dep[q.front()])
q.push_front(to[i]);
else q.push_back(to[i]); //SLF优化
}
}
}
return dep[s]<inf;//dep表示联通性
}
然后是增广的 \(\texttt{dfs(x,F)}\)。这就是zkw费用流和EK的区别之所在。与 \(\texttt{spfa()}\) 不同，这是正着跑图，所以就可以避免 \(dep[]\) 每次增广前都必须重新算的浪费时间。代码：
int dfs(int x,int F){
vis[x]=1; //这里的vis表示联通性，把上面的vis数组清空后回收利用
if(x==t||!F) return F;//如果到终点或者没流量了，逃。
int f,flow=0;
for(auto i:g[x])if(!vis[to[i]]&&fw[i]&&dep[x]-ct[i]
==dep[to[i]]&&(f=dfs(to[i],min(F,fw[i])))>0){
//如果节点没走过，这条边有流量，dep判断层次，保证是低层次向高层次增广，f为递归得到的这条边实际能流的流量
cans+=f*ct[i],fw[i]-=f,fw[i^1]+=f,flow+=f,F-=f; //流，减去正边流量，增加反边可反悔流量，增加一次增广最大流流量，减少来时剩下的流量
if(!F) break; //优化
}
return flow;
}
之所以算 \(cans\) 的时候只需 \(cans+=f\times ct[i]\) 是因为一条增广的流肯定是处处流量相等的。
然后再回来看总体求最小费用最大流的函数，一次 \(\texttt{spfa()}\) 里就可以增广很多路，通过 \(vis[t]\) 判断 \(s\) 到 \(t\) 的流量这次是否流光，即判断 \(s\) 和 \(t\) 的连通性。代码：
void mcmf(){
while(spfa()){
vis[t]=1;
while(vis[t]){
for(int i=1;i<=p;i++) vis[i]=0;
fans+=dfs(s,inf);
}
}
}
总体上，zkw费用流的码量与EK是等同的，但大部分时候快很多。如果你理解了zkw费用流，那么蒟蒻就放代码了：
#include <bits/stdc++.h>
using namespace std;
const int V=1e6;
const int M=3e6;
const int inf=0x3f3f3f3f;
int n,m,s,t,p,fans,cans;
class Graph{
public:
int top,to[M<<1],fw[M<<1],ct[M<<1];
vector<int> g[V];
Graph(){top=1;}
void add(int x,int y,int f,int c){
g[x].push_back(++top);
to[top]=y,fw[top]=f,ct[top]=c;
}
void Add(int x,int y,int f,int c){
add(x,y,f,c),add(y,x,0,-c);
}
};
class zkwMCMF:public Graph{
public:
int dep[V]; bool vis[V];
deque<int> q;
bool spfa(){
for(int i=1;i<=p;i++) vis[i]=0,dep[i]=inf;
q.push_back(t),vis[t]=1,dep[t]=0;
while(q.size()){
int x=q.front();q.pop_front(),vis[x]=0;
for(auto i:g[x])if(fw[i^1]&&dep[to[i]]>dep[x]-ct[i]){
dep[to[i]]=dep[x]-ct[i];
if(!vis[to[i]]){
vis[to[i]]=1;
if(q.size()&&dep[to[i]]<dep[q.front()])
q.push_front(to[i]);
else q.push_back(to[i]);
}
}
}
return dep[s]<inf;
}
int dfs(int x,int F){
vis[x]=1;
if(x==t||!F) return F;
int f,flow=0;
for(auto i:g[x])if(!vis[to[i]]&&fw[i]&&dep[x]-ct[i]
==dep[to[i]]&&(f=dfs(to[i],min(F,fw[i])))>0){
cans+=f*ct[i],fw[i]-=f,fw[i^1]+=f,flow+=f,F-=f;
if(!F) break;
}
return flow;
}
void mcmf(){
while(spfa()){
vis[t]=1;
while(vis[t]){
for(int i=1;i<=p;i++) vis[i]=0;
fans+=dfs(s,inf);
}
}
}
}network;
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t),p=n;
for(int i=1,x,y,f,c;i<=m;i++){
scanf("%d%d%d%d",&x,&y,&f,&c);
network.Add(x,y,f,c);
}
network.mcmf();
printf("%d %d\n",fans,cans);
return 0;
}
最后附上我用EK和zkw费用流提交模板的用时比较：
\(\texttt{EK：}\texttt{1.76s}\)
\(\texttt{zkw费用流：}\color{#44cc44}{\texttt{520ms}}\)
整整快四倍！
祝大家学习愉快！