  A well-studied nonlinear extension of the minimum-cost flow problem is to
minimize the objective $\sum_{ij\in E} C_{ij}(f_{ij})$ over feasible flows $f$,
where on every arc $ij$ of the network, $C_{ij}$ is a convex function. We give
a strongly polynomial algorithm for the case when all $C_{ij}$'s are convex
quadratic functions, settling an open problem raised e.g. by Hochbaum [1994].
We also give strongly polynomial algorithms for computing market equilibria in
Fisher markets with linear utilities and with spending constraint utilities,
that can be formulated in this framework (see Shmyrev [2009], Devanur et al.
[2011]). For the latter class this resolves an open question raised by Vazirani
[2010]. The running time is $O(m^4\log m)$ for quadratic costs,
$O(n^4+n^2(m+n\log n)\log n)$ for Fisher's markets with linear utilities and
$O(mn^3 +m^2(m+n\log n)\log m)$ for spending constraint utilities.
  All these algorithms are presented in a common framework that addresses the
general problem setting. Whereas it is impossible to give a strongly polynomial
algorithm for the general problem even in an approximate sense (see Hochbaum
[1994]), we show that assuming the existence of certain black-box oracles, one
can give an algorithm using a strongly polynomial number of arithmetic
operations and oracle calls only. The particular algorithms can be derived by
implementing these oracles in the respective settings.
