= Solution
Use nonnegative amounts on the original <directed edges> of the <flow network>. A <feasible flow> is a <function> $f:E\to\mathbb R_{\geq0}$ satisfying the <capacity constraints> $f(u,v)\leq c(u,v)$ and <flow conservation> at every internal <vertex>:
$$
\sum_{u:(u,v)\in E}f(u,v)=\sum_{w:(v,w)\in E}f(v,w)\qquad(v\notin\{s,t\}).
$$
Its <flow value> is net outflow at the source,
$$
\boxed{|f|=\sum_{v:(s,v)\in E}f(s,v)-\sum_{u:(u,s)\in E}f(u,s).}
$$
Summing <flow conservation> shows that this is also net inflow at the sink. Subtracting incoming <flow> matters when the source has incoming <edges>.
An $s$–$t$ <cut of a flow network> is a <partition of a set> $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its <cut capacity> is \b[the total outward <flow network edge capacity>],
$$
c(S,V\setminus S)=\sum_{(u,v)\in E:\,u\in S,\,v\notin S}c(u,v).
$$
Incoming <edges> do not contribute to this <sum>. Equivalently, one may use the antisymmetric net-<flow> convention, but the nonnegative arc convention above will also be used in the subsequent reductions.
Back to article page
