大流問題的標號ppt課件(編輯修改稿)
2025-05-26 00:00 本頁面
【文章內容簡介】 結點信息包括標號（前驅結點指針 p，當前可改進量 d）和弧指針 w: ? Ptype=record ? p,d:integer ? w:link。 ? end。 ? Var path:array[1..maxn] of ptype。 ? 隊列：采用寬度優(yōu)先搜索的方法求最大流。 ? Var q:array[1..maxn] of integer。 ? op,cl:integer。 {隊列指針 } ? 構造網絡 D的鄰接表。 ? 每讀入一條?。?u,v）的兩個端點 u,v及其容量 c后，則在D[u]的鄰接表中插入流量為 0，容量為 c的前向?。?u， v）；在 D[v]對應的鄰接表中插入流量為 0，容量為 0的后向弧（ v,u）。這個過程可以用子過程 insert(u,v,c)完成。 ? 構造過程： ? 讀定點數 n，源點序號 s和匯點序號 t； ? For i:=1 to n do d[i]:=nil。 ? While D網未讀完 do ? begin ? 讀入當前弧的兩個端點 u,v及其容量 c； ? insert(u,v,c)； ? end。 ? Procedure insert(u,v,c:integer)。 ? Var x:link。 ? Begin ? x:=d[u]。 ? While (xnil) and(x^.kv) do x:=x^.next。 ? If xnil then x^.c:=c ? Else begin ? new(x)。
教學課件相關推薦
鄂ICP備17016276號-1