Lesson 38 — Network Flow (Max Flow / Min Cut)
Ba module tương tác: Edmonds-Karp animator (BFS tìm augmenting path, bơm flow,
cập nhật residual), Residual graph (cạnh xuôi/ngược + dung lượng dư),
và Min cut (sau max flow, highlight lát cắt tách s/t).
1. Edmonds-Karp animator BFS augment + residual
Mạng s=0 … t=N-1. Bấm Tìm đường BFS để thấy đường tăng luồng ngắn nhất, rồi Bơm flow để đẩy bottleneck dọc đường + cập nhật residual. Lặp tới khi không còn đường → max flow.
source s
sink t
augmenting path
cạnh có flow
Chọn mạng rồi bấm "Tìm đường BFS".
Max flow hiện tại: 0.
Cạnh ghi flow/cap. Khi flow = cap → cạnh bão hòa (không augment xuôi được nữa).
2. Residual graph — cạnh xuôi & ngược vì sao cần undo
Cùng trạng thái flow của Module 1. Residual có cạnh xuôi (dư = c−f) và cạnh ngược (= f, để rút lại flow). Bấm cạnh trong bảng để highlight trên đồ thị.
cạnh xuôi (dư > 0)
cạnh ngược (rút lại)
cạnh xuôi bão hòa (dư 0)
Bấm "Đồng bộ" để xem residual của trạng thái flow hiện tại.
| Cạnh | Loại | Dung lượng dư c_f |
|---|
3. Min cut — lát cắt tách s khỏi t max flow = min cut
Sau khi đạt max flow, BFS từ s trên residual (chỉ cạnh dư > 0). Đỉnh tới được = S, còn lại = T. Cạnh gốc S→T = min cut. Bấm Chạy tới max flow rồi Tìm min cut.
tập S (reach từ s)
tập T
cạnh cut (S→T)
Bấm "Chạy tới max flow".
Max flow = ? |
Min cut capacity = ?