How can I find the minimum cost max-flow in a graph where the capacity of an edge have a lower and upper bound (UPD: Edge have a capacity within a range [l,r])?
UPD: FLOW (not capacity) of an edge have a lower and upper bound
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 3 | awoo | 161 |
| 4 | maroonrk | 152 |
| 4 | nor | 152 |
| 6 | -is-this-fft- | 151 |
| 7 | TheScrasse | 148 |
| 8 | atcoder_official | 146 |
| 9 | Petr | 145 |
| 10 | pajenegod | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.06.2024 03:44:08 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
What do you mean by lower and upper bound? If you mean that the capacity of the edge must always be within a range [l,r], then just set its capacity to r-l and do a normal flow algorithm.
Yes the capacity of an edge is within a range [l,r]. But your idea is not right. See this graph,
1-->2(l=5,r=10,cost=2)2-->3(l=9,r=14,cost=2)Where source is 1 and sink is 3.
Here, the maximum flow is 10 and the cost is 20. But according to your idea the maximum flow is 5 and the cost is 10. Correct me if I'm wrong.
if I remember correctly the lower-bound max flow can be translated into a max-flow without lower-bounds but I'm not sure if it can be applied to costed max flow
Can you please share your idea about how to convert a lower bound max-flow into a max-flow without lower bounds?
http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf
basically construct another graph G' to test if the max flow is possible, than subtract it from the original graph
If the CAPACITY of the edges has to be in the ranges [5,10] and [9,14], then the answer is 5. You send 5 units of flow through the path, the capacity of the first edge decreases to 5 and the capacity of the second edge decreases to 9. No further flow can be sent.
If, on the other hand, the FLOW that goes through the edges has to be in the ranges [5,10] and [9,14], then that's a completely different problem and the solution I suggested wouldn't work. If that's what you're actually asking, you should rephrase your post.
It was my fault. Sorry for the inconvenience. updated the post. Thanks for pointing out my mistake.