大流問(wèn)題的標(biāo)號(hào)ppt課件(編輯修改稿)
2025-05-26 00:00 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 結(jié)點(diǎn)信息包括標(biāo)號(hào)（前驅(qū)結(jié)點(diǎn)指針 p，當(dāng)前可改進(jìn)量 d）和弧指針 w: ? Ptype=record ? p,d:integer ? w:link。 ? end。 ? Var path:array[1..maxn] of ptype。 ? 隊(duì)列：采用寬度優(yōu)先搜索的方法求最大流。 ? Var q:array[1..maxn] of integer。 ? op,cl:integer。 {隊(duì)列指針 } ? 構(gòu)造網(wǎng)絡(luò) D的鄰接表。 ? 每讀入一條?。?u,v）的兩個(gè)端點(diǎn) u,v及其容量 c后，則在D[u]的鄰接表中插入流量為 0，容量為 c的前向弧（ u， v）；在 D[v]對(duì)應(yīng)的鄰接表中插入流量為 0，容量為 0的后向?。?v,u）。這個(gè)過(guò)程可以用子過(guò)程 insert(u,v,c)完成。 ? 構(gòu)造過(guò)程： ? 讀定點(diǎn)數(shù) n，源點(diǎn)序號(hào) s和匯點(diǎn)序號(hào) t； ? For i:=1 to n do d[i]:=nil。 ? While D網(wǎng)未讀完 do ? begin ? 讀入當(dāng)前弧的兩個(gè)端點(diǎn) 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)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1