最大流的pascal标准程序

var

ch2:char

tf,bosstf:boolean

name:string

jd,qn:longint

t,boss,hpboss,bossatt,ene,n,eneatt,my,myatt,hpmy,hpene:integer

i,j,i1,j1,x,y:integer

ch:char

dt:array[0..11,0..11] of string

procedure hpfirst

begin

my:=400

hpmy:=400

myatt:=350

qn:=10

jd:=10

ene:=350

hpene:=350

eneatt:=300

boss:=10000

hpboss:=10000

bossatt:=5000

end

procedure hpfull

begin

inc(hpmy,30)

my:=hpmy

inc(hpene,30)

ene:=hpene

inc(myatt,10)

inc(eneatt,20)

if t=10 then begin inc(qn)inc(jd)end

end

procedure beg

begin

write('制作人：刘志健。')

readln

write('公布网站:bbs.oifans.cn')

readln

write('用户名:liuzhijian')

readln

writeln

writeln

write('游戏开始？')

readln

end

procedure map

begin

for i:=1 to 10 do

for j:=1 to 10 do begin

if j<>10 then write(dt[i,j])

if j=10 then writeln(dt[i,j])

end

end

procedure input

begin

writeln('骑士:',name,' 你的体力:',my)

writeln('H:帮助，M:移动，B:挑BOSS:')

readln(ch)

end

procedure help

begin

writeln('@是没敌人的，*是有敌人的，~是自己，袭则！是宝早袭物。')

writeln('潜能可以伤3倍的血，绝对必杀是必杀招，起初各有十次，后来每战斗十次各加1个。')

readln

end

procedure full

begin

my:=hpmy

ene:=hpene

end

procedure enem

var

ch:string

begin

repeat

writeln('敌人出现！！！！')

writeln('A普通攻击,B使用潜能,C绝对必拍睁棚杀')

readln(ch)

if bosstf then begin

if (ch='a') or (ch='A') then dec(boss,myatt)

if ((ch='b') or (ch='B')) and (qn<>0) then dec(boss,myatt*3)

if ((ch='c') or (ch='C')) and (jd<>0) then dec(boss,boss)

if boss<=0 then begin writeln('战斗胜利！')tf:=trueexitend

dec(my,bossatt)

if my<=0 then begin writeln('游戏结束！')tf:=trueexitend

end

else begin

if (ch='a') or (ch='A') then dec(ene,myatt)

if ((ch='b') or (ch='B')) and (qn<>0) then dec(ene,myatt*3)

if ((ch='c') or (ch='C')) and (jd<>0) then dec(ene,ene)

if ene<=0 then begin writeln('战斗胜利！')t:=t+1breakend

dec(my,eneatt)

if my<=0 then begin writeln('游戏结束！')exitend

end

until 1<>1

if my<=0 then exit

if boss<=0 then exit

fullhpfull

end

procedure move

var

ch2:string

begin

map

writeln('W是上,A是左,S是下,D是右')

readln(ch2)

if (ch2='w') or (ch2='W') then begin

if dt[x+1,y]=' *' then enem

else begin dt[x+1,y]:=' ~'dt[x,y]:=' @'x:=x+1end

end

if (ch2='a') or (ch2='A') then begin

if dt[x,y-1]=' *' then enem

else begin dt[x,y-1]:=' ~'dt[x,y]:=' *'y:=y-1end

end

if (ch2='s') or (ch2='S') then begin

if dt[x-1,y]=' *' then enem

else begin dt[x-1,y]:='~ 'dt[x,y]:=' *'x:=x-1end

end

if (ch2='d') or (ch2='D') then begin

if dt[x,y+1]=' *' then enem

else begin dt[x,y+1]:=' ~'dt[x,y]:=' *'y:=y+1end

end

end

function f(ch:char):integer

begin

if (ch='H') or (ch='h') then help

if (ch='M') or (ch='m') then move

if (ch='B') or (ch='b') then begin bosstf:=trueenemend

end

begin

randomize

hpfirst

beg

write('Your name:')readln(name)

for i:=1 to 10 do

for j:=1 to 10 do begin

n:=random(2)

if n=0 then dt[i,j]:=' @'

if n=1 then dt[i,j]:=' *'

end

i:=random(10)+1

j:=random(10)+1

repeat

i1:=random(10)+1

j1:=random(10)+1

until (i<>i1) or (j<>j1)

x:=i

y:=j

dt[i,j]:=' ~'

dt[i1,j1]:=' !'

repeat

if tf then exit

map

input

f(ch)

until 1<>1

end.

function [f,wf,No]=MaxFlowMinCut_Me(n,C)

% 利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码

% f %显示最大流

% wf %显示最大流量

% No %显示标号, 由此可此芹悄得最小割

% n 节点个数

% C %弧容量

% Example:

% n=8

% C=[0 5 4 3 0 0 0 0

%0 0 0 0 5 3 0 0

%0 0 0 0 0 3 2 0

%0 0 0 0 0 0 2 0

%0 0 0 0 0 0 0 4

%0 0 0 0 0 0 0 3

%0 0 0 0 0 0 0 5

%0 0 0 0 0 0 0 0]

% [f,wf,No]=MaxFlowMinCut_Me(n,C)

for(i=1:n)for(j=1:n)f(i,j)=0endend %取初始可行流f 为零流

for(i=1:n)No(i)=0d(i)=0end %No,d 记录标号

while(1)

No(1)=n+1d(1)=Inf%给发点vs 标号

while(1)pd=1%标号过程

for(i=1:n)if(No(i)) %选择一个已标号的点vi

for(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %对于未给标号森渣的点vj, 当vivj 为首禅非饱和弧时

No(j)=id(j)=C(i,j)-f(i,j)pd=0

if(d(j)>d(i))d(j)=d(i)end

elseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi 为非零流弧时

No(j)=-id(j)=f(j,i)pd=0

if(d(j)>d(i))d(j)=d(i)endendendendend

if(No(n)|pd)breakendend %若收点vt 得到标号或者无法标号, 终止标号过程

if(pd)breakend %vt 未得到标号, f 已是最大流, 算法终止

dvt=d(n)t=n%进入调整过程, dvt 表示调整量

while(1)

if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt%前向弧调整

elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvtend %后向弧调整

if(No(t)==1)for(i=1:n)No(i)=0d(i)=0endbreakend %当t 的标号为vs 时, 终止调整过程

t=No(t)endend%继续调整前一段弧上的流f

wf=0for(j=1:n)wf=wf+f(1,j)end

end

1、augment path，直译为“增广路径”，其思想大致如下：

原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也运迹春就是容量）与E(G)相同。每次 *** 作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此旁耐时辅助图上的正向流就是最大流。

我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由Source到Sink的流都增加了，若容量都是整数，则这个算法必然会结束。

寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。

增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1（假设容量、流为整数），州敬这样会造成性能上的很大问题，解决这个问题有一个复杂得多的算法，就是预推进算法。

2、push label，直译为“预推进”算法。

3、压入与重标记(Push-Relabel)算法

除了用各种方法在剩余网络中不断找增广路(augmenting)的Ford-Fulkerson系的算法外，还有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本 *** 作有：压入，作用于一条边，将边的始点的预流尽可能多的压向终点；重标记，作用于一个点，将它的高度（也就是label）设为所有邻接点的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺点是相对难以理解。

Relabel-to-Front使用一个链表保存溢出顶点，用Discharge *** 作不断使溢出顶点不再溢出。Discharge的 *** 作过程是：若找不到可被压入的临边，则重标记，否则对临边压入，直至点不再溢出。算法的主过程是：首先将源点出发的所有边充满，然后将除源和汇外的所有顶点保存在一个链表里，从链表头开始进行Discharge，如果完成后顶点的高度有所增加，则将这个顶点置于链表的头部，对下一个顶点开始Discharge。

Relabel-to-Front算法的时间复杂度是O(V^3)，还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP，感觉它和Relabel-to-Front本质上没有区别，因为Relabel-to-Front每次前移的都是高度最高的顶点，所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点，每次对pop出来的顶点discharge，出现了新的溢出顶点时入队。

Push-Relabel类的算法有一个名为gap heuristic的优化，就是当存在一个整数0<k<V，没有任何顶点满足h[v]=k时，对所有h[v]>k的顶点v做更新，若它小于V+1就置为V+1。

cpp程序: #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define inf 0x7fffffffusingnamespace stdint tt,kaseint nn,mint H[45],X[1004],P[1004],flow[1004],tot,cap[1005]int d[45]int S,Tvoid add(int x,int y,int z){P[++tot]=yX[tot]=H[x]H[x]=totflow[tot]=zcap[tot]=flow[tot]}queue<int> qbool bfs(){memset(d,0,sizeof(d))d[S]=1 int xq.push(S)while(!q.empty()){x=q.front()q.pop()for(int i=H[x]ii=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1q.push(P[i])}}}returnd[T]}int dfs(int x,int a){if(x==T||a==0)return aint f=a,tmpfor(int i=H[x]ii=X[i]){if(flow[i]>0&&d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a))flow[i]-=tmpa-=tmpflow[i^1]+=tmpif(!a)break}}if(f==a)d[x]=-1return f-a}int Dinic(){int f=0while(bfs())f+=dfs(S,inf)return f}int main(){/**输入过程省略**/int maxflow=Dinic()printf(%d\n,maxflow)return 0}

---