圖論的基本算法(參考版)
2024-10-11 15:10本頁(yè)面
【正文】 k:=nextadj(dig,j,k)。 k:= firstadj(dig,j)。) else [ vl[1..n]:=ve[n]。 if not toporder(dig) then writeln(39。若滿足 e(s)=l(s),則該活動(dòng)為關(guān)鍵活動(dòng) 求關(guān)鍵路徑 PROC critical_path(Var dig:adjlisttp)。 從 ve(1)=0開(kāi)始往前遞推 ve(j)=Max{ve(i)+dut(i,j)} 從 vl(n)=ve(n)開(kāi)始往后遞推 vl(i)=Min{vl(j)dut(i,j)} 算法步驟： 1)輸入 e條弧 j,k建立 AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu) 2)從源點(diǎn) V1出發(fā) ,令 ve[1]=0，按拓?fù)溆行蚯笃溆喔鞫c(diǎn)最早發(fā)生時(shí)間 ve[i]。 這一道試題的時(shí)間復(fù)雜度大致為 O(N2)。 如果 F[I]=F[J]COST[J]（ A[J， I] 0）的話且第 I個(gè)子工程為關(guān)鍵工程，那么第 J個(gè)子工程也是關(guān)鍵工程。動(dòng)態(tài)規(guī)劃方程： F[I]=MAX{F[J]}+COST[I] {A[I， J] 0，第 I子工程必須在子工程 J之后完工 } F[I]表示完成子工程 I所需的最早時(shí)間， COST[I]表示完成子工程 I所需的時(shí)間。如果該圖能夠進(jìn)行拓?fù)渑判虻脑?，證明有解，反之則無(wú)解。第 2行為按由小到大順序輸出所有關(guān)鍵子工程的編號(hào)。每行數(shù)據(jù)之間均用空格分開(kāi)。 ? 第 3行到 N+2行，每行有 N1個(gè) 0或 1。 示例 1 序號(hào) 完成時(shí)間 子工程1 子工程2 子工程3 子工程4 子工程5 子工程1 5 0 0 0 0 子工程2 4 0 0 0 0 子工程3 12 0 0 0 0 子工程4 7 1 1 0 0 子工程5 2 1 1 1 1 約束條件 ? 輸入：第 1行為 N， N是子工程的總個(gè)數(shù)， N≤200。 （ 3）只要滿足子工程間的依賴關(guān)系，在任何時(shí)刻可以有任何多個(gè)子工程同時(shí)在施工，也既同時(shí)施工的子工程個(gè)數(shù)不受限制。為了便于編程，現(xiàn)在我們假設(shè)： （ 1）根據(jù)預(yù)算，每一個(gè)子工程都有一個(gè)完成時(shí)間。 分析 ? 胖陀陀規(guī)定必須在最貴的城市舉辦宴會(huì) ?因此不能簡(jiǎn)單地選擇一條最短路走 ?若路上有一個(gè)花費(fèi)特別貴的城市 … ? 對(duì)于每個(gè)點(diǎn) X，如果在那里辦宴會(huì) … ?如何求最短路？ ?多個(gè)詢問(wèn)怎么處理？ ? floyd計(jì)算每?jī)牲c(diǎn)的距離？ ? SSSP就可以勝任嗎？ ? AB = AX + XB… 關(guān)鍵工程 ? 在大型工程的施工前，我們把整個(gè)工程劃分為若干個(gè)子工程，并把這些子工程編號(hào)為 …… 、 N；這樣劃分之后，子工程之間就會(huì)有一些依賴關(guān)系，即一些子工程必須在某些子工程完成之后才能施工。 ? 瘦陀陀正專注地看回家的地圖 ?地圖上標(biāo)有 n（ n≤200）個(gè)城市和某些城市間直達(dá)的道路 ?以及每條道路的過(guò)路費(fèi) ?瘦陀陀還知道在每一座城市舉辦宴會(huì)的花費(fèi)。 ?綜合起來(lái) ? d[i， j， k]=min{d[i， k， k1]+d[k， j， k1]， d[i， j， k1]} ? 邊界條件是 d[i， j， 0]=w(i， j)（不存在的邊權(quán)為 ∞） floydwarshall算法 ? 基本的動(dòng)態(tài)規(guī)劃 ?把 k放外層循環(huán)，可以節(jié)省內(nèi)存 ?對(duì)于每個(gè) k，計(jì)算每?jī)牲c(diǎn)的目前最短路 for k:=1 to n do for i:=1 to n do for j:=1 to n do if (d[i,k]∞)and(d[k,j]∞) and(d[i,k]+d[k,j]d[i,j]) then d[i,j]:=d[i,k]+d[k,j] ? 一定要背下來(lái)！ ? 時(shí)間復(fù)雜度： O(n3) ? 用途：預(yù)處理！ 一個(gè)例子 ? 一場(chǎng)可怕的戰(zhàn)爭(zhēng)后，瘦陀陀和他的好朋友胖陀陀將要?jiǎng)P旋。 ? 計(jì)算為滿足上述限制需要雇傭的最少出納員數(shù)目 ? 在每一時(shí)刻可以有比對(duì)應(yīng)的 R(i)更多的出納員在工作。 ? R(0)表示從午夜到午夜 1:00需要出納員的最少數(shù)目， ? R(1)表示上午 1:00到 2:00之間需要的 … ? 每一天，這些數(shù)據(jù)都是相同的。 輸出 共有 n行，每行一個(gè)數(shù)據(jù)對(duì)應(yīng)測(cè)試數(shù)據(jù)。 ? s（ 0＜ S≤100）表示城市的個(gè)數(shù)， t表示飛機(jī)單位里程的價(jià)格， A， B分別為城市 A， B的序號(hào)，（ 1≤A， B≤S）。 約束條件 輸入 ? 第一行為一個(gè)正整數(shù) n(0≤n≤10)，表示有 n組測(cè)試數(shù)據(jù)。她知道每個(gè)城市都有四個(gè)飛機(jī)場(chǎng)，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市中兩個(gè)機(jī)場(chǎng)之間有一條筆直的高速鐵路，第 i個(gè)城市中高速鐵路的單位里程價(jià)格為 Ti，任意兩個(gè)不同城市的機(jī)場(chǎng)之間均有航線，所有航線單位里程的價(jià)格均為 t。wm:=dist[i] ] s:=s+[j] for i:=1 to vtxnum do if not (i in s) and (dist[j]+[j,i]wm then [ dist[i]:=dist[j]+[j,i]。 j:=
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1