[proofplan] We first show that the hypothesis of real feasibility already implies the existence of an integral feasible flow of value $b$, by the usual augmenting-path argument with integral residual capacities. Starting from such an integral flow, we repeatedly cancel a negative-cost directed cycle in the residual network, augmenting by the minimum residual capacity along that cycle. Each cancellation preserves the value, preserves integrality, and strictly decreases total cost; since there are only finitely many integral flows bounded by the capacities, the process terminates. The terminal flow has no negative residual cycle, and a residual-decomposition argument proves that this condition is equivalent to minimum cost among all feasible flows of the same value. [/proofplan] [step:Construct an integral feasible flow of value $b$] For a flow $f:A\to\mathbb{R}$, define its value by \begin{align*} |f|:=\sum_{a=(s,w)\in A} f(a)-\sum_{a=(w,s)\in A} f(a). \end{align*} We first prove that there exists a feasible flow $f_0:A\to\mathbb{Z}$ of value $b$. Start with the zero flow $f^{(0)}:A\to\mathbb{Z}$, $a\mapsto 0$. Given an integral feasible flow $f:A\to\mathbb{Z}$ with $|f|<b$, define its residual directed graph $D_f=(V,A_f)$ as follows. For each arc $a=(v,w)\in A$, include the forward residual arc $a^+=(v,w)$ with residual capacity \begin{align*} r_f(a^+):=u(a)-f(a) \end{align*} when $u(a)-f(a)>0$, and include the backward residual arc $a^-=(w,v)$ with residual capacity \begin{align*} r_f(a^-):=f(a) \end{align*} when $f(a)>0$. Since $u(a)$ and $f(a)$ are integers, every residual capacity is an integer. We claim that if a feasible flow of value $b$ exists, then whenever $|f|<b$ there is an $s$-$t$ directed path in $D_f$. Let $g:A\to\mathbb{R}$ be a feasible flow of value $b$. Let $S\subseteq V$ be the set of vertices reachable from $s$ in $D_f$. If $t\notin S$, then every original arc $a=(v,w)$ with $v\in S$ and $w\notin S$ has $f(a)=u(a)$, because otherwise its forward residual arc leaves $S$. Also every original arc $a=(w,v)$ with $w\notin S$ and $v\in S$ has $f(a)=0$, because otherwise its backward residual arc leaves $S$. Define the outgoing boundary arc set $A^+(S):=\{(v,w)\in A:v\in S\text{ and }w\notin S\}$ and the incoming boundary arc set $A^-(S):=\{(w,v)\in A:w\notin S\text{ and }v\in S\}$. Therefore \begin{align*} \sum_{a\in A^+(S)} g(a)-\sum_{a\in A^-(S)} g(a) \leq \sum_{a\in A^+(S)} u(a)=\sum_{a\in A^+(S)} f(a)-\sum_{a\in A^-(S)} f(a). \end{align*} By flow conservation at all vertices of $S\setminus\{s\}$ and by $t\notin S$, the left-hand side equals $|g|=b$, while the right-hand side equals $|f|<b$, a contradiction. Hence $t\in S$, so an $s$-$t$ residual path exists. Choose such a path $P$ and define \begin{align*} \delta:=\min\left(\,b-|f|,\ \min_{e\in P} r_f(e)\right). \end{align*} The number $\delta$ is a positive integer. Augment $f$ along $P$ by adding $\delta$ on original arcs traversed forward and subtracting $\delta$ on original arcs traversed backward. The resulting flow is integral, feasible, and has value $|f|+\delta$. Repeating this operation, the value increases by at least $1$ at each step and never exceeds $b$, so after finitely many steps we obtain an integral feasible flow $f_0:A\to\mathbb{Z}$ of value $b$. [guided] The first issue is that the theorem assumes only the existence of a feasible real-valued flow of value $b$, but the cycle-canceling argument must start from an integral flow. We therefore prove integrality of feasibility directly. For a flow $f:A\to\mathbb{R}$, its value is \begin{align*} |f|:=\sum_{a=(s,w)\in A} f(a)-\sum_{a=(w,s)\in A} f(a). \end{align*} Begin with the zero flow $f^{(0)}:A\to\mathbb{Z}$, $a\mapsto 0$. Suppose we have already constructed an integral feasible flow $f:A\to\mathbb{Z}$ with $|f|<b$. The residual graph $D_f=(V,A_f)$ records all legal infinitesimal modifications of $f$. For each original arc $a=(v,w)\in A$, the forward residual arc $a^+=(v,w)$ has capacity \begin{align*} r_f(a^+):=u(a)-f(a) \end{align*} if $u(a)-f(a)>0$, and the backward residual arc $a^-=(w,v)$ has capacity \begin{align*} r_f(a^-):=f(a) \end{align*} if $f(a)>0$. These capacities are integers because both $u(a)$ and $f(a)$ are integers. Why must there be an $s$-$t$ path in this residual graph while $|f|<b$? Let $g:A\to\mathbb{R}$ be any feasible flow of value $b$, which exists by hypothesis. Let $S\subseteq V$ be the set of all vertices reachable from $s$ in $D_f$. Suppose, for contradiction, that $t\notin S$. Then no residual arc can go from $S$ to $V\setminus S$. Hence if $a=(v,w)\in A$ with $v\in S$ and $w\notin S$, the forward residual capacity must vanish, so $f(a)=u(a)$. Similarly, if $a=(w,v)\in A$ with $w\notin S$ and $v\in S$, the backward residual capacity must vanish, so $f(a)=0$. Define $A^+(S):=\{(v,w)\in A:v\in S\text{ and }w\notin S\}$ and $A^-(S):=\{(w,v)\in A:w\notin S\text{ and }v\in S\}$. Using these two boundary facts and the bounds $0\leq g(a)\leq u(a)$, we get \begin{align*} \sum_{a\in A^+(S)} g(a)-\sum_{a\in A^-(S)} g(a) \leq \sum_{a\in A^+(S)} u(a)=\sum_{a\in A^+(S)} f(a)-\sum_{a\in A^-(S)} f(a). \end{align*} The net flow leaving $S$ equals the total source excess inside $S$. Since $s\in S$, $t\notin S$, and every other vertex satisfies conservation, the left-hand side is $|g|=b$ and the right-hand side is $|f|<b$. This contradiction proves that $t$ is reachable from $s$ in $D_f$. Choose an $s$-$t$ residual path $P$. Define \begin{align*} \delta:=\min\left(\,b-|f|,\ \min_{e\in P} r_f(e)\right). \end{align*} This is a positive integer: $b-|f|$ is a positive integer, and every residual capacity on $P$ is a positive integer. Augmenting by $\delta$ means adding $\delta$ to each original arc used forward by $P$ and subtracting $\delta$ from each original arc used backward by $P$. The definition of residual capacity guarantees that no capacity bound is violated, and conservation is preserved at all internal vertices of $P$. The value increases by exactly $\delta$. Since the value increases by at least $1$ and never exceeds $b$, finitely many augmentations produce an integral feasible flow $f_0:A\to\mathbb{Z}$ of value $b$. [/guided] [/step] [step:Cancel negative residual cycles while preserving integrality and value] Let $f:A\to\mathbb{Z}$ be an integral feasible flow of value $b$. For each residual arc associated to an original arc $a\in A$, define its residual cost by $c_f(a^+):=c(a)$ for the forward residual arc and by $c_f(a^-):=-c(a)$ for the backward residual arc. For a directed residual cycle $C$, define its residual cost by \begin{align*} c_f(C):=\sum_{e\in C} c_f(e). \end{align*} If there is a directed residual cycle $C$ with $c_f(C)<0$, define \begin{align*} \varepsilon:=\min_{e\in C} r_f(e). \end{align*} Since $f$ and $u$ are integral, $\varepsilon$ is a positive integer. Augmenting $f$ by $\varepsilon$ around $C$ gives a new flow $\tilde f:A\to\mathbb{Z}$: add $\varepsilon$ on original arcs traversed forward by $C$ and subtract $\varepsilon$ on original arcs traversed backward by $C$. The residual-capacity definition gives $0\leq \tilde f(a)\leq u(a)$ for every $a\in A$. Because $C$ enters and leaves each of its vertices the same number of times, flow conservation is unchanged at every vertex, and since $C$ is closed, the value remains $b$. The cost difference is \begin{align*} \sum_{a\in A} c(a)\tilde f(a)-\sum_{a\in A} c(a)f(a)=\varepsilon \sum_{e\in C} c_f(e)=\varepsilon c_f(C)<0. \end{align*} Thus each negative-cycle cancellation produces another integral feasible flow of value $b$ with strictly smaller total cost. [/step] [step:Use finiteness to obtain an integral flow with no negative residual cycle] There are only finitely many integral feasible flows, because each arc $a\in A$ satisfies \begin{align*} f(a)\in \{0,1,\dots,u(a)\}. \end{align*} Starting from the integral feasible flow $f_0$ constructed above, repeatedly cancel a negative residual cycle whenever one exists. At each step the total cost strictly decreases, so the same integral flow cannot occur twice. Since the set of integral feasible flows is finite, the process terminates after finitely many steps. Let $f_*:A\to\mathbb{Z}$ be the terminal flow. Then $f_*$ is feasible, has value $b$, and its residual graph contains no directed cycle of negative residual cost. [/step] [step:Show that absence of negative residual cycles implies minimum cost] Let $g:A\to\mathbb{R}$ be any feasible flow of value $b$. Define the signed difference $h:A\to\mathbb{R}$ by \begin{align*} h(a):=g(a)-f_*(a). \end{align*} Because $f_*$ and $g$ have the same value and both satisfy flow conservation away from $s,t$, the function $h$ has zero net divergence at every vertex. More explicitly, for every $v\in V$, \begin{align*} \sum_{a=(v,w)\in A} h(a)-\sum_{a=(w,v)\in A} h(a)=0. \end{align*} Construct a residual circulation $\gamma$ on the residual graph of $f_*$ as follows. If $h(a)>0$, put $\gamma(a^+)=h(a)$ on the forward residual arc associated to $a$; if $h(a)<0$, put $\gamma(a^-)=-h(a)$ on the backward residual arc associated to $a$; all other residual arcs receive value $0$. These arcs exist because $g(a)\leq u(a)$ gives $h(a)\leq u(a)-f_*(a)$ when $h(a)>0$, and $g(a)\geq 0$ gives $-h(a)\leq f_*(a)$ when $h(a)<0$. The zero-divergence identity for $h$ says exactly that $\gamma$ is a nonnegative circulation on the residual graph. Every nonnegative circulation on a finite directed graph decomposes into a finite nonnegative linear combination of directed cycles. Indeed, if $\gamma$ is not identically zero, choose an arc with positive $\gamma$-value and follow positive-flow arcs; conservation prevents the walk from stopping, and finiteness forces a repeated vertex, producing a directed cycle. Subtract the minimum positive $\gamma$-value along that cycle and repeat. This process terminates because at least one positive arc is removed at each subtraction. Therefore there are directed residual cycles $C_1,\dots,C_m$ and positive coefficients $\alpha_1,\dots,\alpha_m\in\mathbb{R}$ such that $\gamma$ is their weighted sum. Since the residual graph of $f_*$ has no negative-cost directed cycle, $c_{f_*}(C_i)\geq 0$ for each $i$. Hence \begin{align*} \sum_{a\in A} c(a)g(a)-\sum_{a\in A} c(a)f_*(a)=\sum_{a\in A} c(a)h(a)=\sum_{e\in A_{f_*}} c_{f_*}(e)\gamma(e)=\sum_{i=1}^m \alpha_i c_{f_*}(C_i)\geq 0. \end{align*} Since $g$ was an arbitrary feasible flow of value $b$, the integral flow $f_*$ has cost no larger than every feasible flow of value $b$. This proves that $f_*$ is a minimum-cost flow of value $b$ and is integral on every arc. [/step]