Hello All.Recently I have been trying to study the Ford-Fulkerson method to compute a maximum network flow in depth , and I can't find out how to prove the following property: After finding an augmenting path in the residual network , the flow-in = flow-out rule will still hold for every node in the network (not including the source and the sink nodes) . Any help on this is appreciated.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | jiangly | 3578 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | tourist | 3565 |
| 8 | maroonrk | 3531 |
| 9 | Radewoosh | 3521 |
| 10 | Um_nik | 3482 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 28.04.2024 18:57:31 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Very good book: "Introduction to Algorithms" Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Of course "the flow-in = flow-out rule will still hold for every node" "After finding an augmenting path". Just finding an augmenting path changes nothing. Each edge still has the same flow. Then for each node from augmenting path we increment flow by value X to one of the it's incoming edge and increment flow by the same value X of one of it's outcoming edges. Obviously, flow-in = flow-out rule will still hold.
Oh , thank you . I have been too blinded.