zkw算法就是在求最短路的基础上进行多路增广的一种算法,是SPFA求最小费用增广路的一种优化算法。其中用距离标号来求最短路,距离标号类似于预流推进算法中的势函数。
算法流程:
将全部距离标号清零,最初子图只有源点。
利用DFS在子图上求最小费用增广路,如果无法求,则转3。
调整距离标号,使得在最小增量的情况下有一个点进入子图,转2,如果无法调整,结束。
代码(从1到n的费用流):
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 2001
int dist[MAXN];
bool f[MAXN];
struct node{
int t,f,c;
node *next,*pair;
} *head[MAXN];
int n,m;
int mincost=0;
void INSERT(int s,int t,int f,int c){
node *p=new(node);
p->t=t;
p->f=f;
p->c=c;
p->next=head[s];
head[s]=p;
}
int aug(int v,int flow){
if (v==n){
mincost+=dist[1]*flow;
return flow;
}
f[v]=false;
int rec=0;
for (node *p=head[v];p;p=p->next){
if (f[p->t]&&dist[v]==dist[p->t]+p->c&&p->f){
int ret=aug(p->t,min(flow-rec,p->f));
p->f-=ret;
p->pair->f+=ret;
if ((rec+=ret)==flow){
return flow;
}
}
}
return rec;
}
bool relabel(){
int rec=0x7fffffff;
for (int i=0;i++<n;){
if (f[i]){
continue;
}
for (node *p=head[i];p;p=p->next){
if (f[p->t]&&p->f){
rec=min(rec,dist[p->t]-dist[i]+p->c);
}
}
}
if (rec==0x7fffffff){
return false;
}
for (int i=0;i++<n;){
if (!f[i]){
dist[i]+=rec;
}
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
head[i]=NULL;
}
while (m--){
int s,t,f,c;
scanf("%d%d%d%d",&s,&t,&f,&c);
INSERT(s,t,f,c);
INSERT(t,s,0,-c);
head[s]->pair=head[t];
head[t]->pair=head[s];
}
memset(dist,0,sizeof(dist));
do {
do {
memset(f,true,sizeof(f));
} while (aug(1,0x7fffffff));
} while (relabel());
printf("%d\n",mincost);
return 0;
}