h2. 'Strigat':problema/strigat

h2. 'Flux':problema/flux

h2. 'Flux':problema/flux
 
Vom forma un sistem de ecuatii in care necunoscutele {$X{~i~}$} vor fi suma fluxurilor de pe drumul de la $0$ la nodul {$i$} (care se garanteaza ca este aceeasi indiferent de drum). Fluxul trimis de la $i$ la $j$ va fi exact n{~i,j~} * ( X{~j~} - X{~i~}) unde n{~i,j~} este numarul de muchii dintre $i$ si {$j$}. Vom pune conditiile de conservare a fluxului pentru fiecare nod {$i$}: suma fluxurilor care intra sa fie egala cu suma fluxurilor care ies. Pentru nodul $1$ nu este necesar sa scriem ecuatia deoarece se stie {$X{~1~}=0$}, iar pentru nodul $N$ vom pune ecuatia suma fluxurilor care intra in el sa fie $1$. Sistemul de {$N-1$} cu {$N-1$} necunoscute se rezolva folosind Gauss.
 
Pana acum am satisfacut conditiile de flux si restrictia impusa de enunt, mai avem doar de satisfacut restrictiile de capacitate de pe fiecare muchie. Observam ca daca pentru ecuatia pentru nodul $N$ in loc de $1$ fixam o valoare $S$ fluxurile trimise pe fiecare muchie se vor inmulti cu $S$. Asadar pentru a satisface conditiile de capacitate trebuie doar sa inmultim fluxurile de pe fiecare muchie cu minimul dintre {$F{~i,j~} / C{~i,j~}$} unde {$F{~i,j~}$} este fluxul trimis pe muchie {$(i,j)$} si {$C{~i,j~}$} este capacitatea muchiei {$(i,j)$}.