Can someone explain (in detail) how can a Linear Programming Problem be converted to a Network Flow problem.
Essentially I wish know how to create the network flow graph given the LP constraints,what edges/vertices to add to the graph and why those edges/vertices are added
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 09:27:54 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by arasmus (previous revision, new revision, compare).
Also , it would be helpful if anyone can suggest such a practice problem.
Where can such a question arise? Not every LP problem can be transformed into a network flow problem (under some natural meaning), network flow LP representation is a very small and strict class.
A general LP problem can define an unbounded feasible set while a network flow LP always defines a bounded polyhedron.
I was actually motivated by this discussion. http://mirror.codeforces.com/blog/entry/45412
But can every network problem be solved by LP?
i came across this comment so you might ask Swistakk
You messed up direction of convertion. As Zlobober says not every LP can be represented as flow. But other way around is surely true. Look at any definition of flow. Variables are flows through every edge. Constraints are of form "influx=outflux" for every vertex and "0<=flow<=capacity" for every edge. Goal is to maximize outflux of source. Everything is perfectly linear, the very definition of flow is already an LP instance, no tweaking needed.