第五节 最小费用最大流

网络流：最小费用最大流（最简单的算法）最小费用流在OI 竞赛中应当算是比较偏门的内容，但是NOI2008 中employee 的突然出现确实让许多人包括zkw 自己措手不及。

可怜的zkw 当时想出了最小费用流模型，可是他从来没有实现过，所以不敢写，此题0 分。

zkw 现在对费用流的心得是：虽然理论上难，但是写一个能AC 题的费用流还算简单。

先贴一个我写的employee 程序：只有不到70 行，费用流比最大流还好写～程序代码:C++#include <cstdio>#include <cstring>using namespace std;const int maxint=~0U>>1;int n,m,pi[550]={0},cost=0;bool v[550]={0};struct etype{int t,c,u;etype *next,*pair;etype(){}etype(int t_,int c_,int u_,etype* next_):t(t_),c(c_),u(u_),next(next_){}void* operator new(unsigned,void* p){return p;}} *e[550],*eb[550];int aug(int no,int m){if(no==n)return cost+=pi[1]*m,m;v[no]=true;for(etype *&i=e[no];i;i=i->next)if(i->u && !v[i->t] && pi[i->t]+i->c==pi[no])if(int d=aug(i->t,m<i->u?m:i->u))return i->u-=d,i->pair->u+=d,d;return 0;}bool modlabel(){int d=maxint,c;for(int i=1;i<=n;++i)if(v[i])for(etype *j=eb[i];j;j=j->next)if(j->u && !v[j->t])if((c=j->c-pi[i]+pi[j->t])<d)d=c;if(d==maxint)return false;for(int i=1;i<=n;++i)if(v[i])pi[i]+=d,e[i]=eb[i];return true;}int main(){freopen("costflow.in","r",stdin);freopen("costflow.out","w",stdout);scanf("%d %d",&n,&m);etype *Pe=new etype[m+m];while(m--){int s,t,c,u;scanf("%d%d%d%d",&s,&t,&u,&c);e[s]=new(Pe++)etype(t, c,u,e[s]);e[t]=new(Pe++)etype(s,-c,0,e[t]);e[s]->pair=e[t];e[t]->pair=e[s];}memmove(eb,e,sizeof(e));do do memset(v,0,sizeof(v));while(aug(1,maxint));while(modlabel());printf("%d\n",cost);return 0;}程序代码:CB大牛翻译的PASCALvarn,m,i,l,s,t,c,cost,u:longint;v:array[0..600]of boolean;dis:array[0..600]of longint;e_n,e_t,e_c,e_u,e_p,e_x:array[0..250000]of longint;function min(a,b:longint):longint;beginif a>b then exit(b);exit(a);end;procedure addedge(s,t,c,u,k:longint);begininc(l);e_n[l]:=e_n[s];e_n[s]:=l;//下一条边e_t[l]:=t;//边的另一端e_c[l]:=c;//边的费用e_u[l]:=u;//边的容量e_p[l]:=l+k;//对应的边end;procedure build(s,t,c,u:longint);beginaddedge(s,t,c,u,1);addedge(t,s,-c,0,-1);end;function aug(no,m:longint):longint;vari,d:longint;beginif no=n then begininc(cost,m*dis[1]);exit(m);end;v[no]:=true;i:=e_x[no];while i<>0 do beginif (e_u[i]>0)and(not v[e_t[i]])and(dis[e_t[i]]+e_c[i]=dis[no]) then begind:=aug(e_t[i],min(m,e_u[i]));if d>0 then begindec(e_u[i],d);inc(e_u[e_p[i]],d);e_x[no]:=i;exit(d);end;end;i:=e_n[i];end;e_x[no]:=i;exit(0);end;function modlabel:boolean;vard,i,j:longint;begind:=maxlongint;for i:=1 to n do if v[i] then beginj:=e_n[i];while j<>0 do beginif (e_u[j]>0)and(not v[e_t[j]])and(e_c[j]-dis[i]+dis[e_t[j]]<d) then d:=e_c[j]-dis[i]+dis[e_t[j]];j:=e_n[j];end;end;if d=maxlongint then exit(true);for i:=1 to n do if v[i] then beginv[i]:=false;inc(dis[i],d);end;exit(false);end;beginassign(input,'coflow.in');reset(input);assign(output,'coflow.out');rewrite(output);readln(n,m);l:=n;for m:=m downto 1 do beginreadln(s,t,u,c);build(s,t,c,u);end;repeatfor i:=1 to n do e_x[i]:=e_n[i];while aug(1,maxlongint)>0 do fillchar(v,sizeof(v),0);until modlabel;writeln(cost);close(output);end.这里使用的是连续最短路算法。

最小费用最大流问题例题讲解
最小费用最大流问题（Minimum Cost Maximum Flow Problem）是一种在特定的多媒体网络中传送给定体积的流量，使总花费最小化的一种算法。

它能满足一些实际生活中的求解，比如电力系统的供求、工厂的物料的分配和两地之间的物品的运输问题，以及更加复杂的产品开发和行业分工中的分布问题等等。

最小费用最大流问题的目标是在满足给定的最大流量要求的前提下，找出具有最小成本的流量方案。

这种问题的解决步骤如下：
1. 在图形中定义网络：用图形表示整个网络，每条边的容量是边上的流量上限。

2. 尝试找出最大流量：在不超过容量限制的前提下，找出输出流量最大的允许方案，也就是最小费用最大流量。

3. 计算最小成本：对所有边的成本进行总结，计算出最小成本。

下面以一个最小费用最大流问题的例题来说明：
假设有一个三角形的网络，它由一个源点S、一个汇点T、一个中间点O以及三条边组成，边的名字分别是SO、OT、OS，它们的容量分别是10、15和5，费用分别是5、3和2。

要求我们在此条件下求解最小费用最大流问题。

解：首先，我们可以求出最大流量：在边SO的容量为10时，我们可以将费用最小的边OT累加，得到最大流量值为10+3=13。

接下来，计算最小费用：根据上述算法，所有边的费用应该都大于等于0，才能累加而得到最大流量。

也就是说，最小费用为
5+3+2=10。

最后，最小费用最大流问题的解为：最大流量13，最小成本10。

最小费用最大流1.最大流问题1.1案例假设现在因为种种原因，我们只能通过地面线路来运输口罩物资，并且每一条线路是有流量限制的。

假设不考虑运输速度，并且源点S （杭州）的口罩物资产量是足够多的，我们需要求解汇点T（武汉）在不计速度的情况下能收到多少物资？对于这个流网络，我们可以轻松的获得汇点T的最大流量。

因为在这个图中，只有两条路径，分别是S → A → B → T和S → C → D → T两条路径来输送流量，前者最大流量是12 ，后者是4，所以最大流量总和是16。

1.2建模图1是连接产品产地Vs和销售地Vt的交通网，每一条弧代表两点间的运输线，弧旁的数字表示这条运输线的最大通过能力。

现在要求制定一个运输方案，使得从Vs运输到Vt的产品数量最多。

图1模型():(,):(,)max .,,,,s ,0,s.t 0,,V V st f c Vf f t f Vμυμυμυυμυυυμμυλμυμυλμλμμμυ∈∈≤∀∈⎧=⎪-=-=⎨⎪≠⎩≥∀∈∑∑其中λ表示总共运输量f μυ表示弧(),μυ中的实际流量(),c μυ表示弧(),μυ中的容量限制S,t 表示物质运输的起点和终点最大流问题的推广现实问题中的网络，不但边有容量，而且点也有容量。

例如运 输网络中表示中转站的点v, 点容量 c(v) 可表示该中转站能容纳的货物的数列。

对点有容量的网络 N ，流函数若满足对一点 v,流入v 的流量之和等于流出v 的流量之和，并且小于等于c(v),2.最小费用最大流问题上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网络上流的费用问题，在许多实际问题中，费用的因素很重要。

例如，在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案。

这就是下面要介绍的最小费用流问题。

在运输网络N = (s,t,V, A,U)中，设(),c μυ是定义在A上的非负函数，它表示通过弧(),μυ单位流的费用。