费用流的定义
费用流：给定一个网络G=(V,E)，每条边(x,y)除了有容量限制c(x,y)，还有一个给定的单位费用w(x,y)。当边(x,y)的流量为f(x,y)时，就要花费f(x,y)*w(x,y)。该网络中总花费最小的最大流被称为"最小费用最大流",总花费最大的最大流被称为"最大费用最大流"，二者合称为"费用流"模型。注意：费用流的前提是最大流，然后才考虑费用的最大值。
类似于"二分图最大匹配"与最大流的关系，"二分图带全匹配"可直接用最大费用流求解，每条边的权值就是它的单位费用。
费用流算法Edmonds-Karp 增广路算法
在EK求解最大流的基础上，把“用BFS寻找任意一条增广路”改为“用SPFA寻找一条单位费用之和最小的增广路”（也就是把w(x,y)当作边权，在残量网络上求最短路）即可求出最小费用最大流。注意：一条反向边(y,x)的费用应设为-w(x,y)，增广路的费用为单位费用之和×增广路的流量。
Edmonds-Karp增广路的实现最小费用最大流
#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=20010;
int head[N],ver[M],nex[M],edge[M],cost[M];
int n,m,tot,flow,maxflow,s,t,ans;
void add(int x,int y,int z,int c){
ver[++tot]=y,edge[tot]=z,nex[tot]=head[x],head[x]=tot,cost[tot]=c;
ver[++tot]=x,edge[tot]=0,nex[tot]=head[y],head[y]=tot,cost[tot]=-c;
}
int d[N],incf[N],pre[N];
bool v[N];
bool spfa(){
queue<int >q;
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[s]=0;
q.push(s);
v[s]=1;incf[s]=1<<30;
while(q.size()){
int x=q.front();
q.pop();
v[x]=0;
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(edge[i]&&d[y]>d[x]+cost[i]){
d[y]=d[x]+cost[i];
q.push(y),v[y]=1;
pre[y]=i;
incf[y]=min(incf[x],edge[i]);
if(y==t)return 1;
}
}
}
return 0;
}
void update(){
int x=t;
while(x!=s){
int i=pre[x];
edge[i]-=incf[t];
edge[i^1]+=incf[t];
x=ver[i^1];
}
maxflow+=incf[t];
ans+=incf[t]*d[t];
}
int main(){
while(cin>>n>>m){
memset(head,0,sizeof(head));
tot=1;
s=1,t=n,maxflow=0,ans=0;
for(int i=1;i<=m;++i){
int x,y,z,c;
cin>>x>>y>>z>>c;
add(x,y,z,c);
}
while(spfa())update();
printf("%d %d\n",maxflow,ans);
}
}
用EK算法求最大费用最大流只需要将SPFA中的d[y]>d[x]+cost[i]改为d[y]<d[x]+cost[i]即可。
