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

Fie un graf orientat cu $N$ noduri si $M$ muchii. $V$ este multimea nodurilor din graf, iar $E$ multimea muchiilor. 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 graf ca fiind o functie _f: E -> Z_. Functia _f_ satisface urmatoarele conditii:

Fie un graf orientat cu $N$ noduri si $M$ muchii. $V$ este multimea nodurilor din graf, iar $E$ multimea muchiilor. 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 graf ca fiind o functie _f: E -> Z_, unde $E$ este multima muchiilor grafului $G$. Functia _f_ satisface urmatoarele conditii:

# este restrictionata de capacitate, adica ∀ ( $i$, $j$) ∈ E avem $f(i,j) ≤ cap(i,j)$

# 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 (&forall; $i$ &isin; $V$ avem <tex>\sum_{(j,i) \in E}^{} f(j,i) = \sum_{(i,k) \in E}^{} f(i,k)</tex>

# fluxul se conserva, adica &forall; $i$ &isin; $V - {1,N}$ valoarea fluxului care intra in nodul respectiv este egala cu valoarea fluxlui care iese din nodul respectiv (&forall; $i$ &isin; $V$ avem <tex>\sum_{(j,i) \in E}^{} f(j,i) = \sum_{(i,k) \in E}^{} f(i,k)</tex>

Valoarea fluxului este <tex>F = \sum_{(1,i) \in E}^{} f(1,i)</tex>, adica fluxul total care pleaca din nodul sursa.

h2. Cerinta
Se cere sa se determine valorile functiei _f_ pentru fiecare muchie (i,j) astfel incat valoarea fluxului sa fie maxima.

h2. Restrictii

* $1 ≤ N ≤ 200$
* $1 ≤ N ≤ 19900$

* $1 ≤ N ≤ 200$
* $1 ≤ M ≤ N*(N-1)$

* capacitatea fiecarei muchii este un numar natural nenul mai mic sau egal cu $10 000 000$.

* daca in fisier exista muchia ({$a$}, {$b$}), cu siguranta nu va exista si muchia ({$b$},{$a$})

* daca exista muchia $(a,b)$ poate sa existe si muchia $(b,a)$

* fluxul maxim va fi ≤ $2 000 000 000$
h2. Exemplu

# se cauta un drum de la sursa (in cazul nostru, nodul $1$) la destinatie (in cazul nostru $N$) cu orice algoritm (bfs, dfs, etc.).
# de pe acest drum se alege muchia de capacitate minima (fie ea $i$)

# din +fiecare+ muchie a drumului ales se scade capacitatea $c~i~$ (astfel muchia $i$ va avea capacitatea $0$ si poate fi ignorata la urmatorii pasi)
# se creste fluxul cu $c~i~$ si se repeta de la pasul $1$

# din +fiecare+ muchie a drumului ales se scade capacitatea $cap{~i~}$ (astfel muchia $i$ va avea capacitatea $0$ si poate fi ignorata la urmatorii pasi)
# se creste fluxul cu $cap{~i~}$

# algoritmul se repeta de la pasul $1$

*Feedback Cosmin:* pune n mare sa se poata implementa si dinic. Ar trebui ceruta eventual si taietura minima, ca multi nu stiu gasi taietura dupa ce au determinat fluxul maxim.
 
h2. Probleme asemanatoare
 
infoarena - "Trafic":http://infoarena.ro/problema/trafic
 

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