主题Maximum flow.ppt

主題：Maximum flow 解題技巧 問題定義 Ford-Fulkerson method Bipartite matching Minimum cost flow 例題講解: A820, A10330, A563, A10080, H91.1 歷年題目 問題定義 給定一個 flow network G=(V, E) directed graph 兩個特殊的 vertex：s (source) 及 t (sink) 每一條 edge (u, v) 上有 capacity c[u, v] 求從 s 到 t 之間最大的運送量(flow) 每條 edge 上的運送量不可以超過該 edge 上的 capacity 問題範例 vertex 表示城市，edge表示高速公路，capacity 表示該段公路最大的運輸量 直覺想法 從 s 往 t 一直送，直到不能再送為止 正確，但需做一些修正 直覺想法再延伸 允許反悔：如果從 u 到 v 有大小為 x 的運送量，表示在這之後從 v 到也可以有至多為 x 的運送量，相反方向的同數量的運送量則會互消 定義flow 運輸量=19 時可能的運法 flow 必須符合以下性質 容量限制：f[u, v] ? c[u, v] 對稱性：f[u, v] = -f[v, u] 守恆性：for all u?V ? {s, t}, 定義: residual graph Rf 定義: augmenting path augmenting path：在 Rf 上任一條從 s 到 t 的 path 使用之資料結構 將 capacity c[i, j]，flow f[i, j] 及 residual graph 的 r[i, j] 以 3 個 n?n 的 matrix 儲存 c[i, j] 在程式執行過程中不會改變 f[i, j] 初始值為 0，每次找到 augmenting path 之後會被更新 r[i, j] = c[i, j] – f[i, j]，找 augmenting path 時會利用到之 matrix 解法: Ford-Fulkerson method 步驟1：把 f 歸零 步驟2： 當 residual graph Rf 還可以找到 augmenting path p 以 augmenting path p 更新 flow f 以 flow f 更新 residual graph Rf 步驟3：回傳 f 找 augmenting path 的方法 從 s 開始做 DFS (depth first search)，找出 s 到 t 的任意一條可能路徑 注意：DFS 是在 residual graph Rf 上做 更新 flow m = min{ f[u, v] | edge (u, v) is on p} for each edge (u, v) on p f[u, v] = f[u, v] + m f[v, u] = - f[u, v] 更新 residual graph 以必威体育精装版的 flow f 更新 residual graph Rf Maximum flow 的大小 計算從 s 流出的 flow 總和 Multiple sources and sinks 增加一個 super-source s，指向所有 si 增加一個 super-sink t，所有 ti 指向它 所有新增的 edge 之 capacity 設為 ? (可設為原圖中所有 capacity 的總和) 例題: A820 網路頻寬 假設在一個網路中有 n 個點，這 n 個點兩兩之間可能有一線路相連且此一連線有流量的限制(各連線不盡相同) 連線的流量是無方向性的(undirected) 給定 s 及 t 兩點，求 s 到 t 之間的最大頻寬，即從 s 到 t 的最大流量 解法: 將 undirected 轉為 directed 例題: A10330 電力輸送問題 從甲城市要輸電到乙城市 中間會經過一些電力轉換站，每個轉換站有本身的電力處理能力上限 各轉換站之間以電纜連接，甲、乙城也各以電纜跟這些轉換站相連，這些電纜各有各的電量流經上限 電纜的電流有方向性 求甲城可輸送到乙城的最大電量 處理點上有流量限制的方法 解法：將每個轉換站拆為兩點 點 a 拆為 a1 及 a2 兩點 a 的 in-edge 連到 a1，a 的 out-edge 連到 a2 新增一條 edge 從 a1 到 a2，上面的 capacity 為 a 點的流量限制 例題: A563 搶匪逃逸路線 有一個城市的街道圖為方形網格，銀行座落在某些交點處 有一群搶匪想要搶銀行(每個人搶的銀行皆不相同) 若逃到網格的外圍點就算逃逸成功，試問他們有沒有互不相交(不能共線或共點)