== 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 $S$ care va fi denumit $sursa$ si nodul $D$, denumit $destinatie$ ({$1 ≤ S,D ≤ N$}). Orice nod $i$ ({$1 ≤ i ≤ N$}) se gaseste pe cel putin un drum de la $S$ la $D$. Definim *fluxul* in graf ca fiind o functie _f: VxV -> 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 $S$ care va fi denumit $sursa$ si nodul $D$, denumit $destinatie$ ({$1 ≤ S,D ≤ N$}). Orice nod $i$ ({$1 ≤ i ≤ N$}) se gaseste pe cel putin un drum de la $S$ la $D$. Definim *fluxul* in graf ca fiind o functie $f$: $VxV$ -> $*Z*$. Functia $f$ satisface urmatoarele conditii:

# 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)$

table(example). |_. flux1.in |_. flux1.out |
| 6 12

1 2 6
1 3 3
3 4 5
4 5 4
5 6 4
3 6 100
2 4 3

4 3
1 3 5

1 5 4

1 3 6
4 6 5
2 3 5
3 6 4
| 13

2 1 3
2 6 5
4 2 6
4 3 3
4 5 4
4 6 6
5 3 4
6 1 5
6 3 100
6 5 4
| 19

|
h2. Indicatii de rezolvare