最大流算法
1. Ford-Fulkerson标号算法（最简单的实现）
分别记录这一轮扩展过程中的每个点的前驱与到该节点的增广最大流量，从源点开始扩展，每次选择一个点（必须保证已经扩展到这个店），检查与它连接的所有边，并进行扩展，直到扩展到t。
Program Ford-Fulkerson;
const
fin='maxstream.in';
fout='maxstream.out';
maxn=1000;
max=1000000000;
type
labeltype=record
father,have:longint;
flag:boolean;
end;
maptype=record
c,f:longint;
end;
var
n,s,t,total:longint;
map:array[1..maxn,1..maxn]of maptype;
vetex:array[1..maxn,0..maxn]of longint;
information:array[1..maxn]of labeltype;
procedure init;
var
i,e,u,v,c:longint;
begin
assign(input,fin);assign(output,fout);
reset(input);rewrite(output);
readln(n,e,s,t);
for i:=1 to e do
begin
readln(u,v,c);
inc(vetex[u,0]);vetex[u,vetex[u,0]]:=v;
inc(map[u,v].c,c);
inc(vetex[v,0]);vetex[v,vetex[v,0]]:=u;
end;
end;
function min(a,b:longint):longint;
begin
if a
else exit(b);
end;
procedure calc;
i,j,m,d,v:longint;
begin
repeat
fillchar(information,sizeof(information),0);
information[s].father:=s;information[s].have:=max;{初始标号}
repeat
i:=1;
while (i<=n) and not((information[i].father<>0)
and(not information[i].flag)) do inc(i);{找到已标号单位检查的点}
if i>n then break;
for j:=1 to vetex[i,0] do{进行扩展}
if (information[vetex[i,j]].father=0)
and((map[i,vetex[i,j]].c<>0)or(map[vetex[i,j],i].c<>0)) then
begin
v:=vetex[i,j];
if (map[i,v].f begin information[v].father:=i; information[v].have:=min(information[i].have,map[i,v].c-map[i,v].f); end; if (map[v,i].f>0) then{存在反向边，容许流量通过} begin information[v].father:=-i; information[v].have:=min(information[i].have,map[v,i].f); end; end; information[i].flag:=true; until information[t].father<>0; if information[t].father=0 then break;{无法增广} d:=information[t].have; m:=t;inc(total,d); repeat{进行增广} j:=m;m:=abs(information[j].father); if information[j].father<0 then map[j,m].f:=map[j,m].f-d; if information[j].father>0 then map[m,j].f:=map[m,j].f+d; until m=s; until false; writeln(total); close(input);close(output); end; begin init; end. 2. 最大容量增广路算法 每次找一条容量最大的增广路来增广，找的过程类似Dijkstra，实现起来相当简单。Program MaxflowArgument; const fin='maxstream.in'; fout='maxstream.out'; maxn=1000; var flag:array[1..maxn]of boolean; map:array[1..maxn,1..maxn]of longint; n,s,t:longint; procedure init; var i,e,v1,v2,c:longint; begin assign(input,fin);assign(output,fout); reset(input);rewrite(output); readln(n,e,s,t);{n为点数,e为边数，默认1为源点，n为汇点} for i:=1 to e do begin readln(v1,v2,c);{v1->v2的容量为c} inc(map[v1,v2],c); end; end; procedure calc; var f,c:longint; procedure findstream;{寻找增广路径，每次找的都是流量最大的那一条} var flag:array[1..maxn]of boolean; have,pr:array[1..maxn]of longint;{have为能扩展此点的最大的流值pr为此点前驱} mi,i,max:longint; begin fillchar(flag,sizeof(flag),false); fillchar(have,sizeof(have),0); have[s]:=2000000000;pr[s]:=0; while true do{用死循环在里面跳出} begin max:=0;mi:=-1; for i:=1 to n do if (not flag[i])and(have[i]>max) then{找当前能扩展出的最大流值，注意：必须是没有被标记过的} begin max:=have[i];mi:=i;end; if mi=-1 then exit;{找不到了，最大流值都为0，根本找不到了，应当退出} if mi=t then break;{推到终点了，应该退出循环} flag[mi]:=true;{标记当前点，免得以后重复访问} for i:=1 to n do if (not flag[i])and(map[mi,i]>=have[i])and(max>=have[i]) then {做出调整，更新推到每一点的流值，更新点必须满足未被标记，并且刚刚标记的点能推到此点并更新此点，因此推倒mi的流要比i的大、mi->i这条边的流量要比原扩展到i的流（即have[i]）也要大，不然无法从mi推到i} begin have[i]:=map[mi,i]; if have[i]>max then have[i]:=max; {have[i]取map[mi,i]与have[mi](max)中较小者} pr[i]:=mi;{重新定义i的前驱} end; end; f:=have[t];i:=t; while pr[i]<>0 do{沿着增广路径倒着回去，把每一条边cut掉已经占用的那一部分，并把相应的反向弧的容量增加} begin dec(map[pr[i],i],f); inc(map[i,pr[i]],f); i:=pr[i]; end; end; begin f:=0;findstream;c:=0; while f<>0 do begin inc(c,f);f:=0;findstream;end;{找增广路径，直到找到最后剩下的增广路径中，流量最大的都为0} writeln(c); close(input);close(output); end; begin init; calc; end. 3. Edmonds-Karp，最短路增广算法的BFS实现 每次找一条最短的增广路，BFS是一个可以很方便的实现思想。 Program EdmondsKarp； const fin='maxstream.in'; fout='maxstream.out'; maxn=1000; max=1000000000; type labeltype=record father,have:longint; flag:boolean; end; maptype=record c,f:longint; end; var n,s,t,total:longint; map:array[1..maxn,1..maxn]of maptype; vetex:array[1..maxn,0..maxn]of longint; information:array[1..maxn]of labeltype; procedure init; var u,v,c,e,i:longint; begin assign(input,fin);assign(output,fout); reset(input);rewrite(output); readln(n,e,s,t); for i:=1 to e do begin readln(u,v,c); inc(vetex[u,0]);vetex[u,vetex[u,0]]:=v; inc(map[u,v].c,c); inc(vetex[v,0]);vetex[v,vetex[v,0]]:=u; end; end; function min(a,b:longint):longint; begin if a else exit(b); end; procedure calc; var q:array[1..maxn]of longint; open,closed,i,j,v,d,m:longint; begin repeat fillchar(information,sizeof(information),0); information[s].have:=max;information[s].father:=s;{初始标记，便于以后操作} open:=0;closed:=1;q[closed]:=s;{初始队列，用BFS实现寻找最短路} while (open begin inc(open);i:=q[open]; for j:=1 to vetex[i,0] do{检查所有边} if (information[vetex[i,j]].father=0) and((map[i,vetex[i,j]].c<>0)or(map[vetex[i,j],i].c<>0)) then begin v:=vetex[i,j]; if (map[i,v].f begin information[v].father:=i; information[v].have:=min(information[i].have,map[i,v].c-map[i,v].f); inc(closed);q[closed]:=v; end; if (map[v,i].f>0) then{存在反向边，容许流量通过} begin information[v].father:=-i; information[v].have:=min(information[i].have,map[v,i].f); inc(closed);q[closed]:=v; end; end; end; if information[t].father=0 then break;{无法增广} d:=information[t].have; m:=t;inc(total,d); repeat{进行增广} j:=m;m:=abs(information[j].father); if information[j].father<0 then map[j,m].f:=map[j,m].f-d; if information[j].father>0 then map[m,j].f:=map[m,j].f+d; until m=s; until false; writeln(total); close(input);close(output); end; begin init; calc; end. 4. 距离标号算法，最短路增广的O(n)寻找实现 使用距离函数d： d[t]=0;d[i]<=d[j]+1若存在(i,j)∈E； 只有路径上满足d[i]=d[i+1]+1的增广路才为满足要求的，一开始我们初始化使标号恰好满足要求，之后不断更改标号使其可以使增广继续。 Program DistanceLable; const fin='maxstream.in'; fout='maxstream.out'; maxn=1000; max=100000000; type link=^node; node=record x,y,c,f:longint; next,back:link; end; var edge:array[1..maxn]of link; d:array[1..maxn]of longint; n,s,t,ans:longint; procedure init; var i,e,v1,v2,c:longint; p,q:link; begin assign(input,fin);assign(output,fout); reset(input);rewrite(output); readln(n,e,s,t); for i:=1 to e do begin readln(v1,v2,c); new(p);p^.x:=v1;p^.y:=v2;p^.c:=c;p^.f:=0;p^.next:=edge[v1];edge[v1]:=p; new(q);q^.x:=v2;q^.y:=v1;q^.c:=0;q^.f:=0;q^.next:=edge[v2];edge[v2]:=q; p^.back:=q;q^.back:=p; end; end; procedure BFS; var open,closed,i,j:longint; q:array[1..maxn]of longint; p:link; begin fillchar(d,sizeof(d),$FF); open:=0;closed:=1;q[1]:=t;d[t]:=0; while open begin inc(open);i:=q[open]; p:=edge[i]; while p<>nil do begin if p^.c=0 then j:=p^.y; if d[j]=-1 then begin d[j]:=d[i]+1; inc(closed);q[closed]:=j; end; end; p:=p^.next; end; end; end; procedure calc; var i,j,k,mink,pathn,delta,minlable:longint; path,cur:array[1..maxn]of link; p:link; begin ans:=0; cur:=edge;pathn:=1;i:=s; while true do begin if i=t then begin mink:=0;delta:=max; for k:=1 to pathn-1 do if path[k]^.c begin mink:=k; delta:=path[k]^.c; end; for k:=1 to pathn-1 do begin dec(path[k]^.c,delta); inc(path[k]^.back^.c,delta); end; pathn:=mink;i:=path[pathn]^.x; inc(ans,delta); end; p:=cur[i]; while p<>nil do begin if p^.c<>0 then begin if d[i]=d[j]+1 then break; end; p:=p^.next; end; cur[i]:=p; if p<>nil then begin path[pathn]:=p;inc(pathn); i:=p^.y; end else begin minlable:=n; p:=edge[i]; while p<>nil do begin if p^.c<>0 then begin j:=p^.y; if d[j] begin minlable:=d[j]; cur[i]:=p; end; end; p:=p^.next; end; d[i]:=minlable+1; if i<>s then begin dec(pathn);i:=path[pathn]^.x; end else if d[i]>n then break; end; end; writeln(ans); close(input);close(output); end; begin init; BFS; calc; end. 5. Dinic，分层思想 对网络分层（按照距t的距离），保留相邻层之间的边，然后运用一次类似于距离标号的方法（其实质是DFS）进行增广。 Program Dinic; const fin='maxstream.in'; fout='maxstream.out'; maxn=1000; max=100000000; type link=^node; node=record x,y,c,f:longint; next,back:link; end; var edge:array[1..maxn]of link; d:array[1..maxn]of longint; n,s,t,ans:longint; procedure init; var i,e,v1,v2,c:longint; p,q:link; begin assign(input,fin);assign(output,fout); reset(input);rewrite(output); readln(n,e,s,t); for i:=1 to e do begin readln(v1,v2,c); new(p);p^.x:=v1;p^.y:=v2;p^.c:=c;p^.f:=0;p^.next:=edge[v1];edge[v1]:=p; new(q);q^.x:=v2;q^.y:=v1;q^.c:=0;q^.f:=0;q^.next:=edge[v2];edge[v2]:=q; p^.back:=q;q^.back:=p; end; end; procedure BFS;{对网络分层} var open,closed,i,j:longint; q:array[1..maxn]of longint; p:link; begin fillchar(d,sizeof(d),$FF); open:=0;closed:=1;q[1]:=s;d[s]:=0; while open begin inc(open);i:=q[open]; p:=edge[i]; while p<>nil do begin if p^.c<>0 then begin j:=p^.y; if d[j]=-1 then begin d[j]:=d[i]+1; inc(closed);q[closed]:=j; if j=t then exit; end; end; p:=p^.next; end; end; end; procedure calc; var i,j,k,mink,pathn,delta:longint; path,cur:array[1..maxn]of link; p:link; begin ans:=0; while true do begin BFS; if d[t]=-1 then break; cur:=edge;pathn:=1;i:=s; while true do{DFS的非递归实现，速度较递归快} begin if i=t then{找到一条增广路，进行增广} begin mink:=0;delta:=max; for k:=1 to pathn-1 do if path[k]^.c begin mink:=k;{mink记录流充满的那条边的前端} delta:=path[k]^.c; end; for k:=1 to pathn-1 do{修改网络} begin dec(path[k]^.c,delta); inc(path[k]^.back^.c,delta); end; pathn:=mink;i:=path[pathn]^.x;{直接回到mink，因为mink的那条边被充满，后面的应该都为0} inc(ans,delta); end; p:=cur[i]; while p<>nil do{找到一条容许边} begin if p^.c<>0 then begin j:=p^.y; if d[i]+1=d[j] then break; end; p:=p^.next; end; cur[i]:=p; if p<>nil then begin{向前推进一步} path[pathn]:=p;inc(pathn); i:=p^.y; end else begin{找不到容许边，退回去} d[i]:=-1; if pathn=1 then break; dec(pathn);i:=path[pathn]^.x; end; end; end; end; procedure print; begin writeln(ans); close(input);close(output); end; begin init; calc; print; end. 二、预留与推进算法 1．一般性算法 随便找个点，要么将他的盈余推出去，要么对他进行重标记，直至无活跃点为止。Program PreflowPush; fin='maxstream.in'; fout='maxstream.out'; maxn=1000; var n,s,t:longint; map:array[1..maxn,1..maxn]of longint; edge:array[1..maxn,0..maxn]of longint; cur,d,e:array[1..maxn]of longint; procedure init; var u,v,c,e,i:longint; begin assign(input,fin);assign(output,fout); reset(input);rewrite(output); readln(n,e,s,t); for i:=1 to e do begin readln(u,v,c); inc(edge[u,0]);edge[u,edge[u,0]]:=v; inc(edge[v,0]);edge[v,edge[v,0]]:=u; inc(map[u,v],c); end; d[s]:=n; for i:=1 to n do cur[i]:=1; end; procedure push(a,b:longint); var x:longint; begin if map[a,b]>e[a] then x:=e[a] else x:=map[a,b]; dec(map[a,b],x);inc(map[b,a],x); dec(e[a],x);inc(e[b],x); end; procedure relable(a:longint); var i,min:longint; begin min:=maxint; for i:=1 to edge[a,0] do if (map[a,edge[a,i]]>0)and(d[edge[a,i]] d[a]:=min+1; end; procedure calc; i,u:longint; begin for i:=1 to edge[s,0] do begin u:=edge[s,i]; inc(e[u],map[s,u]);dec(e[s],map[s,u]); inc(map[u,s],map[s,u]);map[s,u]:=0; end; while true do begin i:=1;while ((i=s)or(i=t)or(e[i]=0))and(i<=n) do inc(i); if i=n+1 then break; while e[i]>0 do begin if cur[i]>edge[i,0] then begin relable(i);cur[i]:=1;end else if (map[i,edge[i,cur[i]]]>0)and(d[i]=d[edge[i,cur[i]]]+1) then push(i,edge[i,cur[i]]) else inc(cur[i]); end; end; writeln(e[t]); close(input);close(output); end; begin init; calc; end. 2．重标记与前移算法 维护一个队列，对一个点不断进行推进与重标记操作，直至其盈余为0，若过程中他没有被重标记过，则可出列，否则加入队头，继续等待检查。 Program RelableToFront; const fin='maxstream.in'; fout='maxstream.out'; maxn=1000; type link=^node; node=record p:longint; next:link; end; var edge:array[1..maxn,0..maxn]of longint; list:link; map,f:array[1..maxn,1..maxn]of longint; e,d,cur:array[1..maxn]of longint; n,s,t:longint; procedure insert(i:longint); var x:link; begin new(x);x^.p:=i; x^.next:=list;list:=x; end; procedure init; var u,v,c,e,i:longint; begin assign(input,fin);assign(output,fout); reset(input);rewrite(output); readln(n,e,s,t); for i:=1 to e do begin readln(u,v,c); inc(edge[u,0]);edge[u,edge[u,0]]:=v; inc(edge[v,0]);edge[v,edge[v,0]]:=u; inc(map[u,v],c); end; d[s]:=n; for i:=1 to n do cur[i]:=1; for i:=1 to n do if (i<>s)and(i<>t) then insert(i); end; procedure push(a,b:longint);{推进操作} var x:longint; begin if map[a,b]>e[a] then x:=e[a] else x:=map[a,b]; dec(map[a,b],x);inc(map[b,a],x); dec(e[a],x);inc(e[b],x); end; procedure relable(a:longint);{重标记操作} var i,min:longint; begin min:=maxint; for i:=1 to edge[a,0] do if (map[a,edge[a,i]]>0)and(d[edge[a,i]] d[a]:=min+1; end; procedure discharge(u:longint);{排除溢出点} begin while e[u]>0 do begin if cur[u]>edge[u,0] then begin relable(u);cur[u]:=1;end{仍然活跃，但是不存在允许边，需重标记} else if (map[u,edge[u,cur[u]]]>0)and(d[u]=d[edge[u,cur[u]]]+1) then push(u,edge[u,cur[u]]){满足要求，可以推进} else inc(cur[u]);{检查下一条边} end; end; procedure calc; var x,tempx:link; u,oldheight,i:longint; begin for i:=1 to edge[s,0] do begin u:=edge[s,i]; inc(e[u],map[s,u]);dec(e[s],map[s,u]); inc(map[u,s],map[s,u]);map[s,u]:=0; end; x:=list; while x<>nil do begin u:=x^.p; oldheight:=d[u]; discharge(u);{检查点u} if d[u]>oldheight then{将点插入队列头} begin tempx:=list; if tempx^.p<>u then begin while tempx^.next<>x do tempx:=tempx^.next; tempx^.next:=x^.next; x^.next:=list;list:=x; end; end; x:=x^.next; end; writeln(e[t]); close(input);close(output); end; begin init; calc; end. 3．最高标号预留与推进算法 记录d值，然后优先处理d值较高的，直至没有盈余。Program HighestLablePreflowPush; const fin='maxstream.in'; fout='maxstream.out'; maxn=1000; max=2*maxn; type listnode=record num:longint; a:array[1..maxn]of longint; end; var n,s,t:longint; map:array[1..maxn,1..maxn]of longint; edge:array[1..maxn,0..maxn]of longint; cur,d,e:array[1..maxn]of longint; list:array[0..2*maxn-1]of listnode; procedure init; var i,j,e,a,b,w:longint; begin assign(input,fin);assign(output,fout); reset(input);rewrite(output); readln(n,e,s,t); fillchar(map,sizeof(map),0); for i:=1 to e do begin readln(a,b,w); inc(map[a,b],w); end; for i:=1 to n do for j:=i+1 to n do if (map[i,j]>0)or(map[j,i]>0) then begin inc(edge[i,0]);inc(edge[j,0]); edge[i,edge[i,0]]:=j;edge[j,edge[j,0]]:=i; end; for i:=1 to n do cur[i]:=1; for i:=0 to n+1 do list[i].num:=0; end; procedure insert(level,x:longint); {加入标号为level的节点x} begin with list[level] do begin inc(num); a[num]:=x; end; end; procedure BFS;{精确计算距离标号} var p,q,i:longint; x:array[1..maxn]of longint; begin for i:=1 to n do d[i]:=max; x[1]:=t;d[t]:=0;q:=1;p:=0; repeat inc(p); for i:=1 to edge[x[p],0] do if d[edge[x[p],i]]=max then begin inc(q);x[q]:=edge[x[p],i]; d[x[q]]:=d[x[p]]+1; if x[q]<>s then insert(d[x[q]],x[q]); end; until p>=q; d[s]:=n; end; procedure push(a,b:longint);{推进操作} var x:longint; begin if map[a,b]>e[a] then x:=e[a] else x:=map[a,b]; dec(map[a,b],x);inc(map[b,a],x); dec(e[a],x);inc(e[b],x); end; procedure relable(a:longint);{重标记操作} var i,min:longint; begin min:=maxint; for i:=1 to edge[a,0] do if (map[a,edge[a,i]]>0)and(d[edge[a,i]] d[a]:=min+1; end; function check(a:longint):boolean;{排出溢出点操作} begin check:=false; while e[a]>0 do begin if cur[a]>edge[a,0] then begin relable(a);check:=true;cur[a]:=1;end else if (map[a,edge[a,cur[a]]]>0)and(d[a]=d[edge[a,cur[a]]]+1) then push(a,edge[a,cur[a]]) else inc(cur[a]); end; end; procedure update(level:longint);{将所有标号level以上的点移除} var j,k:longint; begin for j:=level+1 to n do begin for k:=1 to list[j].num do begin list[n+1].a[list[n+1].num+k]:=list[j].a[k]; d[list[j].a[k]]:=n+1; end; inc(list[n+1].num,list[j].num); list[j].num:=0; end; end; procedure calc; var i,b,level:longint; begin for i:=1 to edge[s,0] do{将所有s出发的弧充满} begin b:=edge[s,i]; e[b]:=map[s,b];dec(e[s],map[s,b]); map[b,s]:=e[b];map[s,b]:=0; end; level:=n; repeat dec(level); with list[level] do begin for i:=num downto 1 do if check(a[i]) then begin if (level>0)and(num=1) then update(level); insert(d[a[i]],a[i]); level:=d[a[i]];a[i]:=a[num];dec(num); break; end; end; until level=0; writeln(e[t]); close(input);close(output); end; begin init; BFS; calc; end. 三、标号的一个缺陷的优化 距离标号法与重标记与前移算法容易退化，所以加一个优化——若存在某一个k(k 这个优化在relable时可以使用，为了节省时间，可以选在每k*n次检查一次。procedure gapheuristic; var count:array[1..maxn*2]of longint; i,j:longint; begin fillchar(count,sizeof(count),0); for i:=1 to n do inc(count[d[i]]); j:=1;while (j if j=n then exit; for i:=1 to n do if i<>s then if (d[i]>j)and(d[i]<=n) then d[i]:=n+1; end; 1459:Power Network Time Limit: 2000MS Memory Limit: 32768K Total Submissions: 17697 Accepted: 9349 Description A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node u may be supplied with an amount s(u) >= 0 of power, may produce an amount 0 <= p(u) <= p max(u) of power, may consume an amount 0 <= c(u) <= min(s(u),c max(u)) of power, and may deliver an amount d(u)=s(u)+p(u)-c(u) of power. The following restrictions apply: c(u)=0 for any power station, p(u)=0 for any consumer, and p(u)=c(u)=0 for any dispatcher. There is at most one power transport line (u,v) from a node u to a node v in the net; it transports an amount 0 <= l(u,v) <= l max(u,v) of power delivered by u to v. Let Con=Σu c(u) be the power consumed in the net. The problem is to compute the maximum value of Con. An example is in figure 1. The label x/y of power station u shows that p(u)=x and p max(u)=y. The label x/y of consumer u shows that c(u)=x and c max(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6. Input There are several data sets in the input. Each data set encodes a power network. It starts with four integers: 0 <= n <= 100 (nodes), 0 <= np <= n (power stations), 0 <= nc <= n (consumers), and 0 <= m <= n^2 (power transport lines). Follow m data triplets (u,v)z, where u and v are node identifiers (starting from 0) and 0 <= z <= 1000 is the value of l max(u,v). Follow np doublets (u)z, where u is the identifier of a power station and 0 <= z <= 10000 is the value of p max(u). The data set ends with nc doublets (u)z, where u is the identifier of a consumer and 0 <= z <= 10000 is the value of 算法分析与设计题目：最大流算法 院系：软件工程 班级：软件11-2班 姓名：慕永利 学号：23 号 目录 1算法提出背景............................................................................................................................- 3 - 2 问题实例及解决.......................................................................................................................- 3 - 3算法论述....................................................................................................................................- 4 - 3.1、可行流..........................................................................................................................- 4 - 3.2 最大流..........................................................................................................................- 5 - 3.3最大流算法.....................................................................................................................- 6 - 3.3.1 增广路径.......................................................................................................- 6 - 3.3.2沿增广路径增广..................................................................................................- 7 - 3.3.3样例：..................................................................................................................- 8 - 3.3.4定理：............................................................................................................... - 13 - 3.3.5算法的实现：................................................................................................... - 13 - 3.3.6 优化.................................................................................................................. - 16 - 4算法应用................................................................................................................................. - 18 - 网络流算法 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 ［问题描述］如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 一、基本概念及相关定理 1)网络与网络流 定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点， 对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 2)可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： 定义2 满足下列条件 (1)容量约束：0≤fij≤cij，(vi,vj)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 3)可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 定义3 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件： 给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从 到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。 可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。 注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧； 收点是指只有弧指向，而没有从它的发出去的弧。 从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。 2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例 最大流算法 clc,clear,M=1000; c(1,2)=3;c(1,4)=3; c(2,3)=1;c(2,4)=20; c(3,6)=3; c(4,5)=10; c(5,1)=4;c(5,3)=2;c(5,6)=13; n=length(u); list=[]; maxf=zeros(1:n);maxf(n)=1; while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[]; index1=(find(u(flag,:)~=0)); label1=index1(find(u(flag,index1)... -f(flag,index1)~=0)); label1=setdiff(label1,record); list=union(list,label1); pred(label1(find(pred(label1)==0)))=flag; maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1)); record=union(record,label1); label2=find(f(:,flag)~=0); label2=label2'; label2=setdiff(label2,record); list=union(list,label2); pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end if maxf(n)>0 v2=n; v1=pred(v2); while v2~=1 if v1>0 网络流常用算法： 1.Fort_Fulkerson算法. 2.Edmonds_Karp算法(最短增广路算法).-------------------O( n*m^2 ) 3.SAP算法(使用距离标号的最短增广路算法).--------------O( n^2*m ) 4.Dinic算法.------------------------------------------O( n^2*m ) 5.Push_Relabel算法(预流推进算法).---------------------O( n^2*m ) 6.FIFO Preflow_Push算法.-------------------------------O( n^2*m) 7.Relabel_to_Front算法.--------------------------------O( n^3 ) 8.Highest Label Preflow_push算法.----------------------O( n^2*m^1/2) 网络流算法讲座材料 1 概念与性质 网络N是指具有以下结构的有向图D，D中有两个称为源和汇的不同顶点s, t，在D的弧集E上定义了非负整数值函数c。 网络N的流是定义在弧集E上的整数值函数，满足对任意边a， 0<=f(a)<=c(a)，且对任意顶点，入流量等于出流量。 性质1：任何st-流都具有如下性质：从s的出流量等于到t的入流量。 性质2：任何st-流都有一个最大流，它可以表示为从s到t，至多E条有向路径集合上的流。 图的切割是将顶点分成两个独立的集合，交叉边是一条连通两个集合中顶点的边，交叉边的集合叫做切割集合。 网络N的st-切割是这样的一个切割，它将源s放到一个集合，将汇t放到另一个集合。与st-切割对应的每条交叉边或者是st-边(从集合s指向集合t)，或者是ts-边(从集合t指向集合s)，st-切割的容量是st-边的容量之和，st-切割的流量等于st-边上的流量和与ts-边上的流量和之差。 性质3：网络中所有st-流的最大值等于所有st-切割的最小容量。 残余网络 边费用是定义在边集E上的整数值函数h。流的费用是该流的所有边的流值与边费用乘积的总和。 最小费用最大流是费用最小的最大流。 性质4：当且仅当残余网络不包含负开销的有向环时，最大流才是一个最小费用流。 2 最大流应用 2.1 一般网络的最大流 描述：给定一个含多个源和多个汇的网络，找出其中的最大流。 解法：在原网络的基础上，增加一个虚源s和一个虚汇t。若原网络有p个源s1, s2, …, sp和q个汇t1, t2, …, tq，则在原网络中增加p条以s为起 网络最大流的算法 网络最大流的算法分类： 一、Ford-Fulkerson增广路方法 1、Ford-Fulkerson标号算法（最简单的实现） 分别记录这一轮扩展过程中的每个点的前驱与到该节点的增广最大流量，从源点开始扩展，每次选择一个点（必须保证已经扩展到这个点），检查与它连接的所有边，并进行扩展，直到扩展到t。 2、最大容量增广路算法 每次找一条容量最大的增广路来增广，找的过程类似Dijkstra，实现起来相当简单。 3、Edmonds-Karp，最短路增广算法的BFS实现 每次找一条最短的增广路，BFS是一个可以很方便的实现思想。 4、距离标号算法 最短路增广的O(n)寻找实现，使用距离函数d：d[t]=0;d<=d[j]+1若存在(i,j)∈E；只有路径上满足d=d[i+1]+1的增广路才为满足要求的，一开始我们初始化使标号恰好满足要求，之后不断更改标号使其可以使增广继续。 5、Dinic，分层思想 对网络分层（按照距t的距离），保留相邻层之间的边，然后运用一次类似于距离标号的方法（其实质是DFS）进行增广。 二、预留与推进算法 1、一般性算法 随便找个点，要么将他的盈余推出去，要么对他进行重标记，直至无活跃点为止。 2、重标记与前移算法 维护一个队列，对一个点不断进行推进与重标记操作，直至其盈余为0，若过程中他没有被重标记过，则可出列，否则加入队头，继续等待检查。 3、最高标号预留与推进算法 记录d值，然后优先处理d值较高的，直至没有盈余。 网络最大流的算法实现 一、Edmonds-Karp（EK）算法 就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE2)，Shortest Augmenting Path (SAP) 是每次寻找最短增广路的一类算法，Edmonds - Karp 算法以及后来著名的Dinic 算法都属于此。SAP 类算法可统一描述如下： Shortest Augmenting Path { x <-- 0 while 在残量网络Gx 中存在增广路s ~> t do { 找一条最短的增广路径P delta <-- min{rij:(i,j) 属于P} 沿P 增广delta 大小的流量 更新残量网络Gx } return x } 在无权边的有向图中寻找最短路，最简单的方法就是广度优先搜索(BFS)，E-K 算法就直接来源于此。每次用一遍BFS 寻找从源点s 到终点t 的最短路作为增广路径，然后增广流量 f 并修改残量网络，直到不存在新的增广路径。 E-K 算法的时间复杂度为O(V*E^2)，由于BFS 要搜索全部小于最短距离的分支路径之后才能找到终点，因此可以想象频繁的BFS 效率是比较低的。实践中此算法使用的机会较少。代码如下： #define VMAX 201 int n, m; //分别表示图的边数和顶点数 int c[VMAX][VMAX]; //容量 int Edmonds_Karp( int s, int t ) //输入源点和汇点 { int p, q, queue[VMAX], u, v, pre[VMAX], flow= 0, aug; while(true) { memset(pre,-1,sizeof(pre)); //记录父节点 for( queue[p=q=0]=s; p<=q; p++ ) //广度优先搜索 { u= queue[p]; for( v=0; v 浅谈网络流算法与几种流模型 吴迪1314010425 摘要：最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。s-t的最大流等于s-t的最小割，最大流最小割定理。网络流在计算机程序设计上有着重要的地位。 关键词：网络流Edmonds-Karp 最大流 dinic 最大流最小割网络流模型最小费用最大流 正文： 图论中的一种理论与方法，研究网络上的一类最优化问题。1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= （V、E、C），其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1 表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。 最大流理论是由福特和富尔克森于 1956 年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。 先来看一个实例。 现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下： 每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？ 这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。 若有向图G=(V,E)满足下列条件： 1、有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。 2、有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。 3、每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。 则称之为网络流图，记为G = (V, E, C) 介绍完最大流问题后，下面介绍求解最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。 三个基本的性质: 如果C代表每条边的容量F代表每条边的流量 一个显然的实事是F小于等于C 不然水管子就爆了 这就是网络流的第一条性质容量限制(Ca pacity Constraints):F 开题报告 数学与应用数学 网络最大流问题算法研究 一、综述本课题国内外研究动态, 说明选题的依据和意义 最大流问题是指在一定的条件下, 要求流过网络的物流、能量流、信息流等流量为最大的问题[2]. 最大流问题已有50多年的研究历史, 这段时期内, 人们建立了最大流问题较 为完善的理论, 同时开发了大量优秀的算法. 如Ford 和Fulkerson 增截轨算法 [3]、Dinic 阻塞流算法、Goldberg 推进和重标号算法[6]以及Goldberg 和Rao 的二分长度阻塞流算法等等, 这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用. 近年来, 随着计算机科学技术和网络的快速发展, 网络最大流问题得到了更深入的研究, 并极大地推动了最大流问题的研究进展. 然而, 研究工作仍未结束: 首先, 在理论算法研究方面, 人们还没有发现最大流问题算法时间复杂度的精确下界, 更没有任何一个通用算法达到或接近问题的下界; 其次, 在算法的实际性能方面, 目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决, 发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决. 因此, 关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig 提出的网络单纯刑法和Ford 和Fulkerson 的增载轨算法, 他们都是伪多项式时间算法, 分别由Dinic, Edmonds 和Karp 等提出. 1973年Dinic 首次获得了时间复杂度的核心因子为nm 算法. 以后的几十年中, 最大流算法获得了很大的进展. 在最大流问题中, ()nm O 时间界是一个自然的障碍. 如果我们把一个流沿从源到汇的各个路径进行分解, 根据流分解定理, 这些包含流的路径的总长度为()nm Θ.因此, 对每次利用一条曾接轨的算法, ()nm O 时间是这类算法的下界. 尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的, 但在很长一段时间内, ()nm O 的 山东科技大学 本科毕业设计（论文）题目最大流问题以及应用 学院名称数学与系统科学学院 专业班级信息与计算科学2011级2班学生姓名吕永强 学号201101051416 摘要 网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。 本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据——Ford-Fulkerson最大流最小割定理；综述解决最大流问题的几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比较各算法在解决不同问题中的优劣。 为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题——铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每辆列车开出的时 刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据，最终解决了问题。 本文采用理论与实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。 Abstract The network flow problem is an important operational research subject. The maximum flow problem is an important content of network flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering，commerce, agriculture, transportation and other areas can bring us great convenience. The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of the maximum flow problem -- Ford-Fulkerson maximum flow minimum cut theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dinic algorithm are summarized in this paper. It also compares various algorithms to solve different problems in the pros and cons. In order to more clearly show the application of the maximum flow problem in the production life, the paper illustrates a real-life problem - -The optimal scheduling of railway freight train to highlight the importance of maximum flow. This instance is to be solved under certain constraints , to design the most freight train numbers through the railway in a day and night and to list out the schedules for each train. In this instance, by abstracting the network diagram from the real problems, transform the actual problem into the maximum flow problem, and use the properties of graph and Ford-Fulkerson labeling algorithm, and ultimately solve the problem. In this paper, the combination of theory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality and 传感技术学报 CHINESE JOURNAL OF SENSORS AND ACTUATORS 第29卷第11期2016年11月Vol 29No.11 Nov.2016Repairing Barrier Gaps in WSN Using Set -Based Max -Flow Algorithm * DAI Guanglin ，FANG Kai ，FANG Fei ，DAI Guoyong ，XIA Ming ， HUAN Ruohong ，MAO Keji * （College of Computer Science and Technology ，Zhejiang University of Technology ，Hangzhou 310023，China ） Abstract ：In wireless sensor networks （WSNs ），barrier coverage is a typical coverage model and is of paramount im?portance for intrusion detection.A barrier divides the area of interest into two regions such that any intruder pene?trates from one region to another is guaranteed to be detected by one or more sensor nodes in the barrier.The emer?gence of a gap in the barrier ，which is caused by running out of energy or other reasons ，may leads to the penetration without being detected.Therefore ，the functions of WSNs will be seriously influenced.A mobile nodes based gap healing method is proposed in this paper.The set -based max -flow algorithm is introduced to efficiently carry out the number of existed gaps and then the mobile nodes are scheduled to the right position to heal the gap under the con?dition of minimizing the total moving distance.Some experiments are conducted and shows the effectiveness of the proposed method.Key words ：WSN ；barrier repairing ；set -based Max -flow algorithm ；efficiency EEACC ：6150P ；6210；7230doi ：10.3969/j.issn.1004-1699.2016.11.019 基于集合最大流算法的WSN 栅栏修复方法研究 *戴光麟，方 凯，方飞，戴国勇，夏明，宦若虹，毛科技*（浙江工业大学计算机科学与技术学院，杭州310023）摘要：无线传感器网络栅栏覆盖在入侵检测方面发挥着重要作用，如何修复栅栏间隙是该领域重点研究问题之一。栅栏将监测区域划分为二部分，任何入侵目标从一个区域穿越到另外一个区域都会被栅栏中至少一个传感器节点监测到。栅栏中的节点由于某些原因过早死亡导致栅栏出现间隙，监测目标可以通过间隙而不被栅栏监测到。提出一种利用移动节点修复栅栏间隙的方法，该方法采用基于集合的最大流算法计算出能修复间隙的数量并且具有较高的效率，然后利用移动节点修复栅栏，修复过程中，移动节点的总移动距离最短。最后仿真实验验证了该方法的有效性。 关键词：无线传感器网络；栅栏修复；集合最大流算法；效率 中图分类号：TP393文献标识码：A 文章编号：1004-1699（2016）11-1742-06 栅栏覆盖是无线传感器网络领域主要的覆盖模型之一，是覆盖控制研究的热点，主要考察监测目标穿越传感器网络时被检测的情况［1］。无线传感器网络栅栏覆盖有着广泛的用途，如在国防应用中，将栅栏部署在边境线可以探测非法越境者。在环保方面，将栅栏部署在污染源周围可检测污染物的扩散情况。在林业保护方面，将栅栏部署在森林火灾现场可检测火灾蔓延情况等［2-4］。 目前国内外对无线传感器网络栅栏覆盖的相关 研究已经取得了很大的成果，栅栏覆盖的概念最早 出现在机器人传感器中［5］。舒坚等人在栅栏覆盖中 合理的引入了移动模型，能够保证以较高的概率发 现入侵者以及提早发现入侵者［6］。Anwar Saipulla 等 人提出了line -based 部署方法，该方法形成栅栏的概 率比均匀部署等方式更高，然后提出2阶段算法修 补栅栏间隙，第一阶段，FIND -GAPS 算法发现栅栏间———————————— 项目来源：国家自然科学基金项目（61379023，61401397，61302129）；浙江省公益性技术应用研究计划项目（2015C31066）；浙 江省安全生产科技计划项目（2013A1001，2013A1002） 收稿日期：2016-03-26修改日期：2016-07-10 万方数据 %最大流算法源程序 clc,clear,M=1000; u(1,2)=1;u(1,3)=1;u(1,4)=2; u(2,3)=1;u(2,5)=2; u(3,5)=1; u(4,3)=3;u(4,5)=3; f(1,2)=1;f(1,3)=0;f(1,4)=1; f(2,3)=0;f(2,5)=1; f(3,5)=1; f(4,3)=1;f(4,5)=0; n=length(u); list=[]; maxf=zeros(1:n);maxf(n)=1; while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[]; index1=(find(u(flag,:)~=0)); label1=index1(find(u(flag,index1)... -f(flag,index1)~=0)); label1=setdiff(label1,record); list=union(list,label1); pred(label1(find(pred(label1)==0)))=flag; maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1)); record=union(record,label1); label2=find(f(:,flag)~=0); label2=label2'; label2=setdiff(label2,record); list=union(list,label2); pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end if maxf(n)>0 v2=n; v1=pred(v2); while v2~=1 if v1>0 f(v1,v2)=f(v1,v2)+maxf(n); else v1=abs(v1); f(v2,v1)=f(v2,v1)-maxf(n);最大流的增广路算法(KM算法).
算法分析与设计(最大流问题)
网络流算法
网络最大流问题概论
从一道题目的解法试谈网络流的构造与算法Word版
图论算法 最大流算法和最大匹配算法
网络流算法讲座材料
最大流算法小结
浅谈网络流算法与几种模型转换
网络最大流问题算法研究【开题报告】
(毕业设计论文)最大流问题及应用
基于集合最大流算法的WSN栅栏修复方法研究
最大流算法源程序