I have to prove that you can turn a maximal preflow (so a preflow, such that the excess of our sink $t$ is maximal) into a maximal flow in $O(mn)$ time.
My first idea was, to take an active node $v$ (which means a node which has positve excess) and randomly decrease the costs of the incoming edges of $v$, until the excess equals $0$. We do that, until there are no active nodes left. However, I am not sure if that already creates a maximal flow. This procedure would be in $O(mn)$, since we iterate over a maximum of $n$ nodes (where $n := |V(G)|$), and in the worst case, every cost of an edge has to be reduced. The problem is, that I don't quite see, why the resulting flow should be maximal. It would be maximal, if there were no more paths from the source $s$ to the sink $t$, but why is this the case here? Maybe, the costs of the edges have to be reduced in a specific way instead of randomly? Can someone give me some advice? Thanks in advance!
Edit: I read something about the Push-Relabel algorithm which basically functions very similar. A better idea would be, to first turn our preflow to an acyclic preflow. This way, we can get a topological order of all nodes, lets say $\{v_1, ... v_n\}$, with $v_1 := t$ and $v_n := s$. Now, we go from $v_2$ to $v_{n-1}$ in the topological order, and check, whether the excess is positive. If it is positive, then we just decrease the incoming flow by reducing the flow on the incoming edges (randomly), until the excess is $0$. This way, only the excess of the next nodes can be affected, so by iterating over all nodes $v_2$ to $v_{n-1}$, the end result will be a flow $f'$. This flow also has the same value as of our preflow, since the incoming edges to the node $t$ didn't change. Since $f$ was a maximal preflow, it follows that $f'$ must be a maximal flow as well.
This sounds like a promising idea, sadly, I do not know how to turn our preflow acyclic. I mean, finding a cycle is possible, but how do I know, which edges can be deleted? It has to be possible in $O(nm)$, since the other steps are in $O(nm)$ as well.