大家好，欢迎来到IT知识分享网。
引言
过去听起来高深莫测的网络流算法，现在已飞入寻常百姓家了，对于每一个OIER，网络流是一个神圣的东西（个人见解），但神圣的同时，它并不是那样抽象，最形象的模型就是水流，从长江源点无限的向外流水，而大海（汇点）则在不断地‘喝水’，当然，你也可以不把它想成水，或者是其他一切可以流动的东西。而事实上，有些东西的流动比较流畅，而某些东西可能相对而言比较粘稠，流速更慢，因此，就产生了一个问题，单位时间内的总流量最多多少，这里会根据流速给定单位时间内的流量，这就是最先开启网络流之门的最大流算法，它的解决方式将在后面谈到，再想一下，如果水管是另一个物流公司所有，那么你会根据从哪里运到哪里付出一定的代价， 为了你自己的利润，显然要找一个在运的东西最多的前提下有最小费用的方案，这就引出了下一个问题，最小费用最大流。再引用某牛一句话“当然也有有钱没处花的傻子，去求最大费用最大流”，而事实上，题目会出现这个模型，为了避免你成为傻瓜，现在你要给它一个新的定义：最大收益流，这时的你，变成了物流公司的经理，而客户的路线由你规划，为了你的钱包，最大收益必不可少。
正文
第一部分.概念性问题(基本定理及定义)
对于一些网络流新手来说，有必要知道一些基本定义和基本定理，这些虽然看起来理论价值不大，但是现在的许多网络流描述需要这些专业性的词语，所以还是 有些了解为好。
首先对于图G
G 的流是一个实值函数 f， f (u, v) 表示顶点 u 到顶点 v 的流，它可以为正， 为零，也可以为负，且满足下列三个性质：
1.容量限制：对所有u, v ÎV ，要求 f (u, v) £ c(u, v) 。 反对称性：对所有u, v ÎV ，要求 f (u, v) =– f (v, u) 。
2.流守恒性：对所有u ÎV –{
s, t} ，要求 å f (u, v) = 0 。
3.整个流网络 G 的流量 f = å f (s, v) 或 f= å f (u, t) 。
接下来定义各种算法中都要用到的一些东东：
1.残留网络
给定一个流网络G = (V , E) 和流 f，由 f 压得的 G 的残留网络Gf= (V , E f ) ，定义 c f (u, v) 为残留网络G f 中边 (u, v) 的容量。如果弧 (u, v) Î E 或弧 (v, u) Î E ，则 弧 (u, v) Î E f ，且 c f (u, v) = c(u, v) – f (u, v) 。
残留网络又被称为剩余图。
2.点的高度和层次，这是两个相对的概念，高度的定义为到汇点的最短路径长度，而层次则是指到源点的最短路径长度（这里的路径长度按照各个边的长度都为1算），这两个量是在最大流算法中贯穿始末的利器。
接下来引入最大流最小割定理
对了，可能有同学还不知道什么是最小割，在这里提一下
流网络 G = (V , E) 的割 (S ,T ) 将V 划分成 S 和T = V – S 两部分，使得 s Î S ，t ÎT 。定义割 (S ,T ) 的容量为 c(S ,T ),
对 于 最 小 的 c ， 它 是 最 小 割 。
3. 最 大 流 最 小 割 定 理
在 流 网 络 中，最 小 割 的 容 量 等 于 最 大 流 的 流 量 。（证 明 再 次 略 过 ）
第二部分.最大流的算法
下面步入与实际问题更加接近的算法实现部分，首先给出问题，给定一个流网络，求源到汇在单位时间内的最大流量。
最简单而效率较好的算法 是基于增广路的算法，这类算法在王欣上大牛的论文中有详细介绍，但我仍然想谈谈我的想法，希望能起到抛砖引玉的作用。基于增广路的算法主要有两种:MPLA,Dinic,SAP.其中最简单的是MPLA,最实用最简洁也是最多人用的是Dinia,SAP的范围也很广，加上GAP优化后的效率也让人咋舌，这也是最近SAP大泛滥的原因吧！个人比较喜欢Dinic，数据变态就用最高标号预流推进，SAP用的比较少，当然，用什么算法还是看你自己的感觉吧。有些人认为增广路算法格式低效，于是想出了对于每个节点操作的算法，这类算法以预留推进为顶梁柱，MPM也勉强归入这一类吧。
1.MPLA算法
即最短路径增值算法，可以有一个简单的思想，每次都找一条从源到汇的路径来增广，直到不能增广为止，之中算法的正确性是可以保证的，但效率不尽如人意，有些时候，把事情格式化反而有益，这里的MPLA就是这样，它只在层次图中找增广路，构建出层次图之后，用BFS不断增广，直到当前层次图中不再有增广路，再重新构建层次图，如果汇点不在层次图内，则源汇不再连通，最大流已经求出，否则继续执行增广，如此反复，就可以求出最大流，在程序实现时层次图不用被构建出来，只需要BFS出各点的距离标号，找路径时判断对于f(u,v)是否有d[u]+1=d[v]即可。
如果每建一次层次图成为一个阶段，则在最短路径增值算法中，最多有N个阶段，证明再次略过。
因此在整个算法中，最多有N个阶段，每个阶段构建层次图的BFS时间复杂度为O(m),建N次，因此构建层次图的总时间为O(mn),而在增广过程中，每一次增广至少删除一条边，因此增广m次，加上修改流量的时间，每一阶段的增广时间为O(m*(m+n)),共有N个阶段，所以复杂度为O(n*m*(m+n))=O(nm^2),这也是该算法的时间复杂度。
2.Dinic算法
MPLA虽然简单，但经常会点超时，我们把增广过程中的BFS改成DFS，效率会有比较大的提高么？答案是肯定的，至此我们已经得到了Dinic的算法流程，只是将MPLA的增广改为DFS，就能写出那美妙的Dinic了，同样，分析一下时间，在DFS过程中，会有前进和后退两种情况，最多前进后退N次，而增广路最多找M次，再加上N个阶段，所以Dinic的复杂度就是O(mn^2)，事实上，它也确实比MPLA快很多，简洁而比较高效，这也是许多OIER选择Dinic的理由了吧，毕竟，写它可能会节省出较长时间来完成其他题目.
1 2 program dinic(input,output); 3 var 4 f : array[0..1000,0..1000] of longint; 5 number : array[0..1000] of longint; 6 q : array[0..10000] of longint; 7 n,m,ans,s,t : longint; 8 procedure init; 9 var 10 x,y,c : longint; 11 i : longint; 12 begin 13 readln(m,n); 14 s:=1; 15 t:=n; 16 fillchar(f,sizeof(f),0); 17 for i:=1 to m do 18 begin 19 readln(x,y,c); 20 inc(f[x,y],c); 21 end; 22 end; { init } 23 function min(aa,bb :longint ):longint; 24 begin 25 if aa<bb then 26 exit(aa); 27 exit(bb); 28 end; { min } 29 function bfs(): boolean; 30 var 31 head,tail : longint; 32 now,i : longint; 33 begin 34 fillchar(number,sizeof(number),0); 35 head:=0; 36 tail:=1; 37 q[1]:=s; 38 number[s]:=1; 39 while head<tail do 40 begin 41 inc(head); 42 now:=q[head]; 43 for i:=1 to n do 44 if f[now,i]>0 then 45 if number[i]=0 then 46 begin 47 number[i]:=number[now]+1; 48 inc(tail); 49 q[tail]:=i; 50 end; 51 end; 52 if number[t]=0 then 53 exit(false); 54 exit(true); 55 end; { bfs } 56 function dfs(now,flow :longint ):longint; 57 var 58 tmp,i : longint; 59 begin 60 if now=t then 61 exit(flow); 62 for i:=1 to n do 63 if number[i]=number[now]+1 then 64 if f[now,i]>0 then 65 begin 66 tmp:=dfs(i,min(flow,f[now,i])); 67 if tmp<>0 then 68 begin 69 inc(f[i,now],tmp); 70 dec(f[now,i],tmp); 71 exit(tmp); 72 end; 73 end; 74 exit(0); 75 end; { dfs } 76 procedure main; 77 var 78 tmp : longint; 79 begin 80 ans:=0; 81 while bfs() do 82 begin 83 tmp:=dfs(s,maxlongint>>2); 84 while tmp<>0 do 85 begin 86 inc(ans,tmp); 87 tmp:=dfs(s,maxlongint>>2); 88 end; 89 end; 90 writeln(ans); 91 end; { main } 92 begin 93 init; 94 main; 95 end.
3.SAP算法
SAP也是找最短路径来增广的算法，有这样一句话：SAP算法更易理解，实现更简单，效率更高，而也有测试表明，SAP加上重要的GAP优化后，效率仅次于最高标号预流推进算法，因此如果你想背一个模板，SAP是最佳选择。SAP在增光时充分的利用了以前的信息，当按照高度找不到增广路时，它会对节点重新标号，h[i]=min{h[j]}+1(c[i,j]>0)，这也是SAP比较核心的思想，而根据这个我们可以发现，当高度出现间隙时，一定不会存在增广路了，算法已经可以结束，因此，这里引入间隙优化(GAP),即出现间隙时结束算法。
在算法实现中，初始标号可以全部置为0，在增广过程中在逐渐提升高度，时间上可能会有常数的增加，但不改变渐进时间复杂度。同时为了简洁，SAP实现时用递归，代码不过80行左右。
1 View Code 2 program sap(input,output); 3 var 4 c : array[0..1000,0..1000] of longint; 5 h,vh : array[0..1000] of longint; 6 flow,n,m,ans : longint; 7 tmpflow : longint; 8 can : boolean; 9 procedure init; 10 var 11 i,j : longint; 12 xx,yy,cc : longint; 13 begin 14 fillchar(c,sizeof(c),0); 15 fillchar(h,sizeof(h),0); 16 ans:=0; 17 readln(m,n); 18 for i:=1 to m do 19 begin 20 readln(xx,yy,cc); 21 inc(c[xx,yy],cc); 22 end; 23 end; { init } 24 procedure dfs(now : longint ); 25 var 26 min,tmp : longint; 27 i : longint; 28 begin 29 min:=n-1; 30 tmp:=tmpflow; 31 if now=n then 32 begin 33 can:=true; 34 inc(ans,tmpflow); 35 exit; 36 end; 37 for i:=1 to n do 38 if c[now,i]>0 then 39 begin 40 if h[i]+1=h[now] then 41 begin 42 if c[now,i]<tmpflow then 43 tmpflow:=c[now,i]; 44 dfs(i); 45 if h[1]>=n then 46 exit; 47 if can then 48 break; 49 tmpflow:=tmp; 50 end; 51 if h[i]<min then 52 min:=h[i]; 53 end; 54 if not can then 55 begin 56 dec(vh[h[now]]); 57 if vh[h[now]]=0 then 58 h[1]:=n; 59 h[now]:=min+1; 60 inc(vh[h[now]]); 61 end 62 else 63 begin 64 dec(c[now,i],tmpflow); 65 inc(c[i,now],tmpflow); 66 end; 67 end; { dfs } 68 begin 69 init; 70 fillchar(vh,sizeof(vh),0); 71 vh[0]:=n; 72 while h[1]<n do 73 begin 74 tmpflow:=maxlongint>>2;; 75 can:=false; 76 dfs(1); 77 end; 78 writeln(ans); 79 end.
4.MPM算法
这个算法我还没有实践过，因为它的实现过程比较繁琐，而且时间效率不高，是一个只具有理论价值的算法，这个算法每次都处理单独节点，记每个节点入流和与出流和的最小值作为thoughput(now)（定义在非源汇点），每次先从now向汇推大小为thoughput(now)的流量，在从点now向源点拉大小为thoughput(now)的流量，删除该节点，继续执行直到图中只剩下源汇。时间复杂度为O(n^3)，但时间常数较大，时间效率不高。
5.预留推进算法
以上的算法中，基本上都需要从大体上来把握全局，而预留推进算法则是将每一个顶点看作了一个战场，分别对他们进行处理，在处理过程中，存在某些时间不满足流量收支平衡，所以对预先推出的流叫做预流，下面来看算法如何将预流变成最大流的。
预留推进算法有两个主过程，push和relabel，即推进和重标号，它是在模拟水流的过程，一开始先让源的出弧全部饱和，之后随着时间的推移，不断改变顶点的高度，而又规定水流仅能从高处流向低处，所以在模拟过程中，最终会有水流入汇，而之前推出的多余的水则流回了源，那么我们每次处理的是什么节点呢？把当前节点内存有水的节点称为活跃节点，每次对活跃节点执行推流操作，直到该节点不再活跃，如果不能再推流而当前节点仍未活跃节点，就需要对它进行重新标号了，标号后再继续推流，如此重复，直到网络中不再存在活跃节点为止，这时源的流出量就是该网络的最大流。注意，对于活跃节点的定义，不包括源汇，否则你会死的很惨。
朴素的预留推进的效率还过得去，最多进行nm次饱和推进和n^2m次不饱和推进，因此总的时间复杂度为O(mn^2)
事实上，如同增广路算法引入层次图一样，定下一些规则，可以让预留推进算法有更好的时间效率，下面介绍相对而言比较好实现的FIFO预留推进算法，它用一个队列来保存活跃节点，每次从队首取出一个节点进行推进，对一个节点relabel之后把它加到队尾，如此执行，直到队列为空，这样一来，预留推进算法的时间复杂度降为O(n^3),实现的时候，可以加上同样的间隙优化，但注意，出现间隙时不要马上退出，将新标号的的高度置为n+1，继续执行程序，这样会让所有的剩水流回源，满足流量收支平衡，以便最后的统计工作。
1 View Code 2 program preflow(input,output); 3 var 4 f,c : array[0..2000,0..2000] of longint; 5 q,h,vh,e : array[0..2000] of longint; 6 m,n,s,t : longint; 7 flow : longint; 8 procedure init; 9 var 10 i,j : longint; 11 xx,yy,cc : longint; 12 begin 13 readln(m,n); 14 fillchar(f,sizeof(f),0); 15 fillchar(c,sizeof(c),0); 16 fillchar(e,sizeof(e),0); 17 for i:=1 to m do 18 begin 19 readln(xx,yy,cc); 20 inc(c[xx,yy],cc); 21 end; 22 s:=1; 23 t:=n; 24 end; { init } 25 procedure main; 26 var 27 i,j : longint; 28 head,tail : longint; 29 now,tmp,tmph : longint; 30 begin 31 flow:=0; 32 h[s]:=n; 33 head:=0; 34 tail:=0; 35 for i:=1 to n do 36 begin 37 e[i]:=c[s,i]; 38 f[s,i]:=c[s,i]; 39 f[i,s]:=-f[s,i]; 40 if (e[i]>0)and(i<>t) then 41 begin 42 inc(tail); 43 q[tail]:=i; 44 inc(vh[h[i]]); 45 end; 46 end; 47 while head<tail do 48 begin 49 inc(head); 50 now:=q[head]; 51 for i:=1 to n do 52 if (c[now,i]>f[now,i])and(h[now]=h[i]+1)and(e[now]>0) then 53 begin 54 tmp:=c[now,i]-f[now,i]; 55 if tmp>e[now] then 56 tmp:=e[now]; 57 inc(f[now,i],tmp); 58 dec(f[i,now],tmp); 59 dec(e[now],tmp); 60 inc(e[i],tmp); 61 if (e[i]=tmp)and(i<>s)and(i<>t) then 62 begin 63 inc(tail); 64 q[tail]:=i; 65 end; 66 end; 67 if (e[now]>0)and(now<>s)and(now<>t) then 68 begin 69 tmph:=h[now]; 70 dec(vh[tmph]); 71 h[now]:=$FFFF; 72 for i:=1 to n do 73 if (c[now,i]>f[now,i])and(h[now]>h[i]+1) then 74 h[now]:=h[i]+1; 75 inc(tail); 76 q[tail]:=now; 77 inc(vh[h[now]]); 78 if vh[tmph]=0 then 79 for i:=1 to n do 80 if (h[i]>tmph)and(h[i]<n) then 81 begin 82 dec(vh[h[i]]); 83 h[i]:=n; 84 inc(vh[n]); 85 end; 86 end; 87 end; 88 flow:=0; 89 for i:=1 to n do 90 inc(flow,f[s,i]); 91 end; { main } 92 begin 93 init; 94 main; 95 writeln(flow); 96 end.
下面介绍最后一个，也是编程难度最大，时间表现不同凡响的算法，最高标号预流推进，它的思想是既然水是从高处向低处流的，那么如果从低处开始会做许多重复工作，不如从最高点开始流，留一次就解决问题。再直观一些，引用黑书上的话“让少数的节点聚集大量的盈余，然后通过对这些节点的检查把非饱和推进变成一串连续的饱和推进”。在程序现实现时，用一个表list来储存所有的活跃节点，其中list(h)存储高的为h的活跃节点，同时记录一个level,为最高标号，每次查找时依次从level,level-1……查找，直到找到节点为止，这时从表内删掉这个节点，对它进行Push,Relabel操作，直到该节点不再活跃，继续进行，直到表内不在存在活跃节点。
它的复杂度为O(n^2*m^(1/2)),时间效率很优秀（当然，如果你刻意构造卡预留推进的数据，它比MPLA还慢也是有可能的）。
1 View Code 2 program hign_node_flow(input,output); 3 var 4 c : array[0..1000,0..1000] of longint; { 保存原图} 5 f : array[0..1000,0..1000] of longint; { 保存当前的预流图} 6 h : array[0..1000] of longint; { 保存各个节点当前高度} 7 vh : array[0..1000] of longint; { 保存各个高度节点的数量} 8 e : array[0..1100] of longint; { 保存各个节点的盈余} 9 level : longint; { 当前所有活跃节点的最高高度} 10 l : array[0..1000,0..1000] of longint; { 保存活跃节点的表,l[i,0]表示高度为i的活跃节点数，这也是不能用vh数组的原因} 11 n,m,s,t : longint; { 节点数，边数，源，汇} 12 listsum : longint; { 记录当前在表内的元素个数} 13 flow : longint; { 记录流量} 14 inlist : array[0..1000] of boolean; { 节点是否在表内} 15 q : array[0..10000] of longint; { 用于BFS扩展的队列} 16 procedure init; 17 var 18 i,xx,yy,cc : longint; 19 begin 20 readln(m,n); 21 fillchar(f,sizeof(f),0); 22 fillchar(c,sizeof(c),0); 23 fillchar(e,sizeof(e),0); 24 fillchar(h,sizeof(h),0); 25 fillchar(vh,sizeof(vh),0); 26 for i:=1 to m do 27 begin 28 readln(xx,yy,cc); 29 inc(c[xx,yy],cc);{ 注意某些情况下有重边，这样处理比较保险} 30 end; 31 s:=1; 32 t:=n; 33 end; { init } 34 procedure insect(now :longint ); { 在活跃节点表内插入节点now} 35 begin 36 inlist[now]:=true; { 标记now节点在表内} 37 inc(listsum); { 表中元素增加1} 38 inc(l[h[now],0]); { 高度为h[now]的活跃节点数增加1} 39 l[h[now],l[h[now],0]]:=now; { 表中高度为h[now]的第l[h[now],0]个活跃节点为now} 40 if h[now]>level then { 更新活跃节点最高高度} 41 level:=h[now]; 42 end; { insect } 43 procedure bfs(); { 利用BFS(反向的)，求的各个节点的高度} 44 var 45 head,tail,i : longint; 46 begin 47 head:=0; 48 tail:=1; 49 q[1]:=t; 50 h[t]:=1; { 汇点的高度为1} 51 while head<tail do 52 begin 53 inc(head); 54 for i:=1 to n do 55 if c[i,q[head]]>0 then { 存在边} 56 if h[i]=0 then { i节点高度没有求出} 57 begin 58 h[i]:=h[q[head]]+1; { 求的节点i的高度} 59 inc(tail); 60 q[tail]:=i; 61 end; 62 end; 63 end; { bfs } 64 procedure previous(); { 预流推进的预处理} 65 var 66 i : longint; 67 begin 68 for i:=1 to n do 69 begin 70 e[i]:=c[s,i]; { 让源点的出弧饱和，则弧的指向点的盈余要改变} 71 f[s,i]:=c[s,i]; { 源点出弧饱和} 72 f[i,s]:=-f[s,i]; { 反向弧的处理} 73 if (e[i]>0)and(i<>t)and(not inlist[i]) then { 节点i成为活跃节点,且不是汇点，没有在表内(其实也不可能在表内)} 74 insect(i); 75 end; 76 h[1]:=n; 77 for i:=1 to n-1 do 78 inc(vh[h[i]]); 79 end; { previous } 80 function find(level :longint ):longint; { 传入当前活跃节点集合的最高高度} 81 var 82 i : longint; 83 begin 84 for i:=level downto 1 do { 枚举节点集合} 85 if l[i,0]<>0 then { 存在节点} 86 begin 87 find:=l[i,l[i,0]]; { 返回表的尾元素} 88 inlist[l[i,l[i,0]]]:=false; { 返回节点不再表内} 89 dec(l[i,0]); 90 dec(listsum); { 表中元素个数减一} 91 while (l[level,0]=0)and(level>0) do { 更新level的值} 92 dec(level); 93 exit; 94 end; 95 exit(0); { 没有找到节点就返回0} 96 end; { find } 97 procedure push(now :longint ); { 推流操作} 98 var 99 i : longint; 100 tmp : longint; 101 begin 102 for i:=1 to n do 103 if (c[now,i]>f[now,i])and(h[now]=h[i]+1)and(e[now]>0) then { 如果当前节点有盈余且有出弧不饱和} 104 begin 105 tmp:=c[now,i]-f[now,i]; { tmp记录对弧而言能增广的量} 106 if tmp>e[now] then { 这里能增广的量=min(tmp,盈余)} 107 tmp:=e[now]; 108 inc(f[now,i],tmp); { 增广操作} 109 dec(f[i,now],tmp); 110 inc(e[i],tmp); { 修改节点盈余} 111 dec(e[now],tmp); 112 if (not inlist[i])and(e[i]=tmp)and(i<>t) then { 接受流的节点一定成为活跃节点且不再表内，又不是汇点} 113 insect(i); 114 end; 115 end; { push } 116 procedure relable(now : longint ); { 重新标号} 117 var 118 i : longint; 119 tmph : longint; 120 begin 121 tmph:=h[now]; { tmph保存未重新标号前now节点的高度} 122 dec(vh[tmph]); { 高度为h[now]的节点数减一} 123 h[now]:=$ffff; { 高度要取min(j)c[now,j]>0,则先赋值最大} 124 for i:=1 to n do 125 if (c[now,i]>f[now,i])and(h[now]>h[i]+1) then 126 h[now]:=h[i]+1; { 更新标号的过程} 127 inc(vh[h[now]]); { 新产生节点的高度记录进去} 128 if vh[tmph]=0 then { GAP优化，如果存在间隙，则最大流已求出} 129 for i:=1 to n do 130 if (h[i]>tmph)and(h[i]<n) then { 让各个节点均抬高到n} 131 begin 132 dec(vh[h[i]]); 133 h[i]:=n; 134 inc(vh[n]); 135 end; { 不能直接退出，否则会无限执行且不满足流量平衡} 136 if (now<>s)and(now<>t) then 137 insect(now);{ now经过PUSH过程已经不再活跃节点内了，且一定有盈余,但一定要保证now不是源，汇} 138 end; { ralable } 139 procedure main; 140 var 141 tmp : longint; 142 begin 143 while listsum<>0 do { 当表中存在活跃节点时} 144 begin 145 tmp:=find(level); { 找到最高标号点} 146 push(tmp); { 推进} 147 if e[tmp]>0 then { 如果推进后该节点还有盈余} 148 relable(tmp); { 重新标号该节点} 149 end; 150 end; { main } 151 procedure print; 152 var 153 i : longint; 154 begin 155 flow:=0; 156 for i:=1 to n do { 累加源的出流量} 157 inc(flow,f[s,i]); 158 writeln(flow); 159 end; { print } 160 begin 161 init; 162 bfs(); 163 previous; 164 main; 165 print; 166 end.
小结：
网络流的最大流算法种类繁多，时间效率编程复杂度也不尽相同，对于不同的流网络，选择相应的算法，需要在不断实践中摸索，这也是一个菜鸟到大牛的必经之路。在一般题目中，选用Dinic是一个不错的想法，但当我们发现网络特别稠密时，FIFO的预留推进算法就要派上用场了，而时间比较紧但题目数据弱，我们甚至可以采用搜索找增广路的算法。
提供最大流测试网址：http://hzoi.openjudge.cn/never/1003/
第三部分 最小费用最大流问题
学习了网络流的最大流算法，一定有一种十分兴奋的感觉，那么，就让你借着这股兴奋劲儿，来学习这一章的最小费用流吧。
最小费用流有两种经典的算法，一种是消圈算法，另一种则是最小费用路增广算法。
第一种，消圈算法。如果在一个流网络中求出了一个最大流，但对于一条增广路上的某两个点之间有负权路，那么这个流一定不是最小费用最大流，因为我们可以让一部分流从这条最小费用路流过以减少费用，所以根据这个思想，可以先求出一个最大初始流，然后不断地通过负圈分流以减少费用，直到流网络中不存在负圈为止。
消圈算法的时间复杂度上限为O(nm^2cw),其中c是最大流量，w为非用最大值，而按特定的顺序消圈的时间复杂度为O(nm^2logn)。这里的时间复杂度分析是按照用bellman-ford算法消圈得到的，用SPFA应该可以得到更优的实际运行时间。
第二种，最小费用路增广算法。这里运用了贪心的思想，每次就直接去找s到t的最小费用路来增广，这样得到的结果一定是最小费用，实现较简单，时间复杂度O(mnv)，v为最大流量。用SPFA效果极好，但鉴于SPFA的不确定性，有时为了保险，往往运用重新加权技术，具体实践请通过网络或其他途径获得。
最小费用流的东西并不多，事实上是使用最短路径这种特殊的网络流解决了普遍的网络流问题，只要掌握好基础，程序不难写出。
1 View Code 2 program minflow(input,output); 3 var 4 f : array[0..501,0..501] of longint; 5 c : array[0..501,0..501] of longint; 6 min,pre,d : array[0..1000] of longint; 7 q : array[0..2000] of longint; 8 v : array[0..501] of boolean; 9 m,n,s,t : longint; 10 procedure init; 11 var 12 xx,yy,cc,dd : longint; 13 i : longint; 14 begin 15 readln(n,m); 16 fillchar(f,sizeof(f),63); 17 fillchar(c,sizeof(c),0); 18 for i:=1 to n do 19 f[i,i]:=0; 20 for i:=1 to m do 21 begin 22 readln(xx,yy,cc,dd); 23 f[xx,yy]:=dd; 24 c[xx,yy]:=cc; 25 f[yy,xx]:=-dd; 26 end; 27 s:=1; 28 t:=n; 29 end; { init } 30 function argument():boolean; 31 var 32 head,tail : longint; 33 i,now : longint; 34 begin 35 for i:=1 to n do 36 d[i]:=maxlongint>>2; 37 fillchar(v,sizeof(v),false); 38 fillchar(min,sizeof(min),63); 39 head:=0; 40 tail:=1; 41 q[1]:=s; 42 v[1]:=true; 43 d[1]:=0; 44 while head<tail do 45 begin 46 inc(head); 47 v[q[head]]:=false; 48 now:=q[head]; 49 for i:=1 to n do 50 if c[now,i]<>0 then 51 begin 52 if d[now]+f[now,i]<d[i] then 53 begin 54 d[i]:=d[now]+f[now,i]; 55 pre[i]:=now; 56 if c[now,i]<min[now] then 57 min[i]:=c[now,i] 58 else 59 min[i]:=min[now]; 60 if not v[i] then 61 begin 62 inc(tail); 63 q[tail]:=i; 64 v[i]:=true; 65 end; 66 end; 67 end; 68 end; 69 if d[t]=maxlongint>>2 then 70 exit(false); 71 now:=t; 72 while now<>s do 73 begin 74 dec(c[pre[now],now],min[t]); 75 inc(c[now,pre[now]],min[t]); 76 now:=pre[now]; 77 end; 78 end; { argument } 79 procedure main; 80 var 81 ans : longint; 82 begin 83 ans:=0; 84 while argument() do 85 inc(ans,min[t]*d[t]); 86 writeln(ans); 87 end; { main } 88 begin 89 init; 90 main; 91 end.
第四部分 网络流算法的应用
一． 最大流问题。
一般情况下，比较裸的最大流几乎不存在，网络流这种东西考得就是你的构图能力，要不然大家背一背基本算法就都满分了，下面介绍一道比较典型的最大流问题。
问题一：最小路径覆盖问题。
题目链接：http://hzoi.openjudge.cn/never/1004/
最小路径覆盖=|P|－最大匹配数
而最大匹配数可以用匈牙利，也可以用最大流，而两者在这特殊的图中，效率是相同的，而一旦题目有一些变化，网络流可以改改继续用，而匈牙利的局限性较大。
问题二：奶牛航班。
Usaco的赛题，以飞机上的座位作为流量限制，通过实际模型的构建，最终运用最大流算法解决，详解可参考国家集训队论文，具体哪年的忘记了，囧。
最大流实在难已以找到比较有意思的题目，下面进入应用最广泛的最小费用流吧！
二.最小费用流问题（最大收益流问题）
这个问题的模型很多下面就此解析几道例题。
问题一：N方格取数
在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2 个数所在方格没有公共边，且取出的数的总和最大。
解析：这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。
结论:最大点权独立集 = 所有点权 – 最小点权覆盖集 = 所有点权 – 最小割集 = 所有点权 – 网络最大流。
问题还有许多，可以参考网上的网络流与线性规划24题，里面题目比较全面（虽然好多根本用不到网络流）。
最后再提一道题目，说一下最小割的转化建模。
The last问题：黑手党
题目大意：要用最少的人数来切断从A到B的所有路径，每个人只能切断一条边。
分析：显然是一个从A到B的最小割问题，由最大流最小割定理，求A到B 的最大流即可。
结论：网络流问题博大精深，难点在构图，这是一种能力，需要逐渐培养。
总结：关于网络流的介绍到这里也就结束了，但是网络流绝不是仅仅这点东西的，由于个人水平问题，出错或片面的地方还请大牛指正。
参考资料：
[1].国家集训队论文2007 王欣上，浅谈基于分层思想的网络流算法。
[2].国家集训队论文2002，江鹏，从一道题目的解法试坛网络流的构造与算法。
[3].算法艺术与信息学竞赛，刘汝佳，黄亮。
[转] http://www.cnblogs.com/neverforget/archive/2011/10/20/2210785.html
———–
注：预留推进算法Gap优化：
度为t，则可以把所有高度在( t, |V| ]之间的点的高度
全部提升到|V|+1
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/144038.html
