演算法筆記(真的是神<_ _>)有簡潔明瞭的概念介紹

實作的話可以看這裡:https://github.com/chichunchen/Algorithm/blob/master/assignment6/Ford-Fulkerson.cpp

其實看完程式碼後,會覺得ford-fulkerson其實挺簡單明瞭的。

用兩張圖,一張圖記錄流量的最大上限,一張圖紀錄剩餘的流量。

用DFS或是BFS找出擴充路徑(s到t的路上,所有路徑的剩餘流量>0)

找到一條的話,就把這條路徑上的邊加上流量,減少剩餘

一直找,找到找不到為止。

results matching ""

    No results matching ""