h3. Pasul 2

Urmatorul pas este sa bagam flux in graful creat (subraf a retelei reziduale). Acesta operatie se poate face usor cautand drumuri de crestere si pompand flux pe aceste drumuri pana cand nu mai gasim nici un drum.

Urmatorul pas este sa bagam flux in graful creat (subraf a retelei reziduale). Acesta operatie se poate face usor cautand drumuri de crestere si pompand flux pe aceste drumuri pana cand nu mai gasim nici un drum. Dupa ce s-a gasit un drum *NU* se face o reactualizare a formei grafului creat la pasul 1, ci doar asupra capacitatilor muchiilor.
 
Observatie: daca am gasit un drum de la sursa la destinatie atunci fluxul maxim pe care il pot pompa prin acest drum de crestere este maximul dintre capacitatile muchiilor de pe drum.
 
O imbunatatire semnificativa este sa se tina cont ca unele drumuri au un inceput comun. Sa presupunem drumurile $sursa -> ...(drum)... -> nod -> ...(drum 1)... -> destinatie$ si $sursa -> ...(drum)... -> nod -> ...(drum 2)... -> destinatie$. Cele doua drumuri au in comun portiunea $sursa -> ...(drum)... -> nod$. Daca drumurile sunt cautate cu un DFS recursiv, atunci dupa ce se ajunge in $nod$ cu posibilitatea de a pompa maxim $C$ flux, si dupa ce introduc $B$ flux pe primul drum, pe al doilea drum mai pot baga cel mult $C-B$ flux.
 
== code(c) |
int do_df(int node, int cap) {
	if (cap == 0)
		return 0;
	if (node == D)
		return cap;
 
	int bag = 0;
	for (int i = 1; i <= edges[node][0]; ++i) {
		const int next = edges[node][i];
		if (flow[node][next] == 0)
			continue;
 
		const int r = do_df(next, min(cap-bag, flow[node][next]));
		if (r) {
			flow[node][next] -= r;
			flow[next][node] += r;
			bag += r;
		}
	}
 
	return bag;
}
==