What should be the approach to find all paths with maximum flow? The graph is directed acyclic graph and the maximum number of nodes(vertices) in the graph can be 40 and edges around 80. Also, most of the edges have unit capacity.
→ Обратите внимание
До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
2 дня
Зарегистрироваться »
Codeforces Round 940 (Div. 2) and CodeCraft-23
2 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 7 | SecondThread | 150 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.04.2024 10:13:10 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Flow isn't fixed on a single path, that's quite trivial... but okay: maxflow along a path is just the minimum of capacities of its edges, so you want to find the maximum capacity c such that there's at least one path from the source to the sink (binseach+BFS) using only edges with capacity ≥ c, then only take edges with capacity ≥ c and find the number of paths — for DAGs, it can be found by a simple DP.
Thanks a lot !!!
I had the same question, but I'm not sure I understand the above answer.
Is there any way you could expand on this Xellos? Wont this solution only find paths for a single iteration of the maximum flow problem by finding some maximum C? I guess I'm not understanding how you handle cases where leaving more in the residual graph will allow for an overall higher maximum.
The idea of a dynamic programming solution makes sense to me, but it seems like we would still end up with a hefty exponential time (although probably improved from factorial) runtime. Any elaboration would be greatly appreciated.
Thank you.
Once you know the value of the max flow, i.e. c, as Xellos pointed out, you can calculate the number of paths from source to sink by DP. You remove all the edges with capacity < c from the graph as they can't be on a path that provides max flow. Now, to calculate the number of paths, you can first topologically sort the graph (it's a DAG, so it's possible) and then compute the dp values in the topologically sorted order. DP[source] = 1. For all others,
.
Correct me if I am wrong.