Exercise 7.21 (Finding a feasible solution)

Suppose we are given a min-cost flow problem. It suffices that we add a super-source and a super-sink, add edges (s, super-sink) for $s\in \text{sinks}$ with capacity $-b_s$ and (super-source, s) for $s\in \text{sources}$ with capacity $b_s$. Note that max-flow will always be less than ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{s\in \text{sources}}{b}_s$ and if there is a feasible solution to the min-cost problem, then that flow is optimal in max-flow. And if max-flow is equal to the upperbound, then that gives us a feasible solution to the min-cost problem.