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