== include(page="template/taskheader" task_id="flux1") ==

*Feedback astronomy:* Fa enuntul clar, pune clar exact definitiile de la flux, adica pentru fiecare muchie sa se gaseasca F(u,v) <= C(u,v) astfel incat sa se respecte proprietatea aia cu suma fluxurilor care ies egala cu suma care intra, ca in nodul sursa nu intra nici o muchie etc.

Fie un graf orientat cu $N$ noduri si $M$ muchii. Asociem fiecarei muchii $(u,v)$ o capacitate nenegativa $cap(u,v)$. Consideram doua varfuri speciale: nodul $1$ care va fi denumit $sursa$ si nodul $N$, denumit $destinatie$. Orice nod $i$ ($2 ≤ i ≤ N-1$) se gaseste pe cel putin un drum de la $1$ la $N$. Definim *fluxul* in $G$ ca fiind o functie _f: VxV -> Z_, unde $V$ este multimea nodurilor grafului. Functia _f_ satisface urmatoarele conditii:

Se da un graf orientat cu $N$ noduri si $M$ muchii, fiecare muchie avand o capacitate data. Se cere sa se determine fluxul maxim de la nodul $1$ (sursa) la nodul $N$ (destinatie).

# este restrictionata de capacitate, adica ∀ $i$, $j$ ∈ V avem $f(i,j) ≤ cap(i,j)$
# este antisimetrica, adica ∀ $i$, $j$ ∈ V avem $f(i,j) = -f(j,i)$
# fluxul se conserva, adica &forall; $i$ &isin; $V$ valoarea fluxului care intra in nodul respectiv este egala cu valoarea fluxlui care iese din nodul respectiv (<tex>\sum_{(i,j) \in V}^{} f(i,j) = 0</tex>)
 
Valoarea fluxului este <tex>\sum_{(i,j) \in V}^{} f(i,j)</tex>, adica suma fluxlul total care pleaca din sursa.
 
 
h2. Cerinta
 
Se cere sa se determine valorile functiei _f_ pentru orice muchie (i,j) astfel incat $F$ sa fie maxim.

h2. Date de intrare