Network flow
- 1. Network Flow Sang Jo Kim
- 2. network flow? Graph weight , capacity朱 螳 豢螳 螳 flow襯 capacity覲企 螳朱 覲企 Graph
- 4. network flow Example Directed Graph螳 覲 旧願鹸 Undirected Graph 螳
- 5. network flow
- 6. network flow 煙 1. f(u, v) c(u, v) 2. u , = (, ) 3. f(u, v) = - f(v, u)
- 7. network flow 覲危 Network flow 蟲伎 蟆 Maximum flow 螳讌 覦覯 螻, 襷 ろ語 郁規れ 郁規 蟆 譴 譴 蟆 襷 Max Flow襯 蟲 蟆 蟾 螳.
- 8. Ford Fulkerson algorithm Max Flow襯 蟲 螳 蠍一 螻襴讀 1. S T襦 螳 讀螳 蟆暑(augmenting path, c(u, v) > f (u, v)) 襯 覓願碓 谿城 2. 讀螳 蟆暑 譴 c(u, v) f(u, v) 螳 螳 螳(Edge)襯 谿 . 螳 F .
- 9. Ford Fulkerson algorithm Max Flow襯 蟲 螳 蠍一 螻襴讀 3. 蟆暑 覈 螳 F襷殊 豢螳. 讀, 覈 蟆暑 螳 f(u, v) += F 蠍一 f(v, u) -= F 豬. 4. 螻殊 伎 讀螳 蟆暑螳 蟾讌 覦覲.
- 10. Ford Fulkerson algorithm Ex) 1.
- 11. Ford Fulkerson algorithm Ex) 2. 蠏碁 螻
- 12. Ford Fulkerson algorithm Ex) 3. 螻
- 13. Ford Fulkerson algorithm Ex) 4. 螻 伎 ?
- 14. Ford Fulkerson algorithm Ex) 5. 螳 蟆 襷る? c(E, A) f(E, A) > 0 覲企 !
- 15. Ford Fulkerson algorithm Ex) 6. 企蟆 覲企 .! 讀, E A襷 1 豢螳朱 覲企 蟆暑襯 覦蟆 蟆!
- 16. Ford Fulkerson algorithm 蠏碁る 讀螳蟆暑(augmenting path)襯 企 蟆 谿場 蟆企? DFS. 襷る DFS襯 伎狩. DFS 螳覲旧°螳 O(V+E)企襦, f覯 蟆暑 襯 谿城り 覃 O(fE)手 .
- 17. Ford Fulkerson algorithm
- 18. Ford Fulkerson algorithm 蠏碁る 讀螳蟆暑(augmenting path)襯 企 蟆 谿場 蟆企? 襷る BFS襯 覃 . O(VE^2) https://www.acmicpc.net/problem/6086