所谓ZKW费用流，其实就是Dinic。
若干年前有一个人发明了最小增广路算法，每次用BFS找一条增广路，时间O(nm^2)
然后被DinicD飞了：我们为什么不可以在长度不变时多路增广呢？时间O(n^2m)
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int inf=1e9;
const int maxn=;
const int maxm=;
struct Dinic {
int n,m,s,t;
int d[maxn],vis[maxn],first[maxn],cur[maxn],next[maxm];
struct Edge {int from,to,flow;}edges[maxm];
Dinic() {
m=;
memset(first,-,sizeof(first));
}
void AddEdge(int from,int to,int cap) {
edges[m]=(Edge){from,to,cap};next[m]=first[from];first[from]=m++;
edges[m]=(Edge){to,from,};next[m]=first[to];first[to]=m++;
}
int BFS() {
memset(vis,,sizeof(vis));
queue<int> Q;Q.push(s);d[s]=;vis[s]=;
while(!Q.empty()) {
int x=Q.front();Q.pop();cur[x]=first[x];
ren {
Edge& e=edges[i];
if(e.flow&&!vis[e.to]) vis[e.to]=,d[e.to]=d[x]+,Q.push(e.to);
}
}
return vis[t];
}
int DFS(int x,int a) {
if(x==t||!a) return a;
int flow=,f;
for(int& i=cur[x];i!=-;i=next[i]) {
Edge& e=edges[i];
if(d[e.to]==d[x]+&&(f=DFS(e.to,min(e.flow,a)))) {
e.flow-=f;edges[i^].flow+=f;
a-=f;flow+=f;if(!a) break;
}
}
return flow;
}
int solve(int s,int t) {
this->s=s;this->t=t;int ans=;
while(BFS()) ans+=DFS(s,inf);
return ans;
}
}sol;
int main() {
int n=read(),m=read();
rep(,m) {
int a=read(),b=read(),c=read();
sol.AddEdge(a,b,c);
}
printf("%d\n",sol.solve(,n));
return ;
}
于是可以用到费用流里来：我们为什么不可以在s到t最短路不变时多路增广呢？
实现做法要从t逆向做SPFA，然后多路增广，具体可以见代码
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int inf=1e9;
const int maxn=;
const int maxm=;
struct ZKW {
int n,m,s,t,cost,ans;
int d[maxn],vis[maxn],first[maxn],inq[maxn],next[maxm];
struct Edge {int from,to,flow,cost;}edges[maxm];
void init(int n) {
this->n=n;m=;
memset(first,-,sizeof(first));
memset(inq,,sizeof(inq));
}
void AddEdge(int from,int to,int cap,int cost) {
edges[m]=(Edge){from,to,cap,cost};next[m]=first[from];first[from]=m++;
edges[m]=(Edge){to,from,,-cost};next[m]=first[to];first[to]=m++;
}
int BFS() {
rep(,n) d[i]=inf;
queue<int> Q;Q.push(t);d[t]=;
while(!Q.empty()) {
int x=Q.front();Q.pop();inq[x]=;
ren {
Edge& e=edges[i^];
if(e.flow&&d[e.from]>d[x]+e.cost) {
d[e.from]=d[x]+e.cost;
if(!inq[e.from]) inq[e.from]=,Q.push(e.from);
}
}
}
rep(,m) edges[i].cost+=d[edges[i].to]-d[edges[i].from];
cost+=d[s];return d[s]!=inf;
}
int DFS(int x,int a) {
if(x==t||!a) {ans+=cost*a;return a;}
int flow=,f;vis[x]=;
ren {
Edge& e=edges[i];
if(e.flow&&!e.cost&&!vis[e.to]&&(f=DFS(e.to,min(e.flow,a)))) {
e.flow-=f;edges[i^].flow+=f;
a-=f;flow+=f;if(!a) break;
}
}
return flow;
}
int solve(int s,int t) {
this->s=s;this->t=t;ans=cost=;
while(BFS()) do memset(vis,,sizeof(vis));while(DFS(s,inf));
return ans;
}
}sol;
int main() {
int n=read(),m=read();sol.init(n);
rep(,m) {
int a=read(),b=read(),c=read(),d=read();
sol.AddEdge(a,b,c,d);
}
printf("%d\n",sol.solve(,n));
return ;
}