最小费用最大流
最小费用最大流：
首先orz一下我的poj2516，本来编出来的118行代码可以ac，但我忘了去掉万恶的debug导致2wa，2ce（poj上的c++编译器不允许动态分配数组大小）
网上大多是讲解什么是网络流，以及各种最大流的算法，但很少有人讲解最小费用最大流，作为蒟蒻的偶，偶觉得有必要提一下最小费用最大流算法，防止蒟蒻的偶以后忘掉了。（本文前提：了解什么事网络流，什么事dinic算法，什么是spfa，以及跟随偶膜拜以下神牛：wzc1995、applepi、liyudong、北航的barty神牛，尤其感谢barty神牛，本人的代码很大部分是“参考”他的）
众所周知，dinic算法的核心有两个，一个是bfs的层次图，另一个是dfs的多路推进求可增广路。其中bfs所求的层次图是作为dfs的遍历要素。
而在最小费用最大流中，我们同样需要求出一条可增广路来，并且我们要求在经过many、many次增广后，所需要的费用最小（以上&&以下的各种常识性错误，叙述错误请无视）。根据贪心的原则，如果我们每次选择最小费用的增广路，如果最后和一般的dinic算法达到的最大流相同的话，我们可以认为此时根据贪心原则增广出来的网络流费用最小。P.s如果存在两条路径所得到的流量相同的话，显然我们要选择花费更小的那一条。那么代码设计如下：
Spfa（）
先写出spfa算法，将判断处改为
如果（u-->v）cost[u]+cc[u,v]0//可增广且路径上的费用系数更小，则记录pre，和此时的cnt(如果用的是邻接表的话)
Augument()
由于spfa（）中求出了一条到汇点的费用系数最小的可增广路，那选取整条路径上最
小流量，在对整条路径的可用流量更新。
代码：
Poj2516最小费用
翻译：有m个供货仓库，n个收货站，k种货物以及m与n之间的每运一份货物的费用系数，求出满足所有收货站要求的最小花费。
输入：多cases。
n，m，k，以下n行，第i行第j列为i-th收货站需要j-th货物zz个
以下m行第i行第j列为i-th供货仓库站需要j-th货物zz个
以下k个n×m的矩阵：第i行第j列为j-th供货仓库供应每份-th货物到i-th的收货站的费用系数为zz。（你敢不仔细看题！！）
输出：如果可以满足所有收货站的要求，输出最小费用，否则输出-1.
分析：最裸地最小费用最大流，其实不管有多少种货物，每个分别计算即可。
P.s：用邻接表建立“初图”（个人称呼方式），“初图”中只包含边图的连接关系以及边的费用，之后用矩阵保存流量。
代码：
#include"iostream"
#include"cstring"
#include"cstdio"
#include"cstdlib"
#defineINF1000000000
#defineN1000
usingnamespacestd;
intn,m,k;
intS,T,nn;//n-->ordersm-->supply
intned[N][N],can[N][N];
intflow[N][N];
intcnt,fa[N*N],t[N*N],ne[N*N],cc[N*N];
//flow图cost图
inlinevoidadd(intx,inty,intw){
cc[cnt]=w,t[cnt]=y,ne[cnt]=fa[x],fa[x]=cnt++;cc[cnt]=-w,t[cnt]=x,ne[cnt]=fa[y],fa[y]=cnt++;}
intpre[N+N];
intq[N*N],he,ta;
boolv[N+N];
intdis[N+N],path[N*N];
inlineboolspfa()
{
memset(dis,127,sizeof(int[nn+10]));
dis[q[ta++]=S]=(v[S]=true)+(pre[S]=-1);while(he
inttmp=q[he++];
for(inti=fa[tmp];~i;i=ne[i])
if(flow[tmp][t[i]]&&dis[tmp]+cc[i]
dis[t[i]]=dis[tmp]+cc[i];
pre[t[i]]=tmp;
path[t[i]]=i;
if(!v[t[i]]){
v[t[i]]=true;
q[ta++]=t[i];
}
}
v[tmp]=false;
}
returndis[T]!=dis[T+1];
}
inttot,want;
intaugument()
{
intdelta=INF,res=0;
for(inti=T;~pre[i];i=pre[i])
delta=min(delta,flow[pre[i]][i]);
for(inti=T;~pre[i];i=pre[i]){
flow[pre[i]][i]-=delta;
flow[i][pre[i]]+=delta;
res+=cc[path[i]]*delta;
}
tot+=delta;
returnres;
}
inlineintdinic_cost()
{
intret(0);tot=0;
while(spfa())ret+=augument();
if(tot==want)
elsereturn0;
}returnret;
intmain()
{
while(scanf("%d%d%d",&n,&m,&k),n+m+k){
S=0,T=n+m+1;
for(inti=1;i
scanf("%d",&ned[i][j]);
for(inti=1,tmp;i
scanf("%d",&can[i][j]);
nn=n+m+1;
boolflag=true;
intans=0;
//cout
cnt=want=0;
if(flag){//重建flow
memset(fa,-1,sizeof(int[n+m+10]));//puts("orders:");
for(inti=1;i
flow[i+m][T]=ned[i][ii];
want+=ned[i][ii];
flow[T][i+m]=0;
add(i+m,T,0);
//printf("%d-->%d:%d\n",i+m,T,0);}
//puts("supply:");
for(inti=1;i
flow[S][i]=can[i][ii];
flow[i][S]=0;
add(S,i,0);
//printf("%d-->%d:%d\n",S,i,0);}
for(inti=1;i
for(intj=1;j
flow[i][j+m]=100000;
flow[j+m][i]=0;
}
}
//puts("between:");
for(inti=1,tmp;i
for(intj=1;j
scanf("%d",&tmp);
add(j,i+m,tmp);
//printf("%d-->%d:%d\n",j,i+m,tmp);}
intz=0;
if(flag)z=dinic_cost();
//cout
if(!z)flag=false;
ans+=z;
}
if(!flag)puts("-1");
elseprintf("%d\n",ans);
}
return0;//cost重建//j-->supplyi-->orders;
}