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
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Apr/20/2026 22:10:02 (g2).
Desktop version, switch to mobile version.
Supported by
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.