Diferențe pentru problema/push-relabel între reviziile #4 si #12

== include(page="template/taskheader" task_id="push-relabel") ==

Se dă un graf orientat complet cu $N$ noduri. Fiecare muchie are atașată o capacitate întreagă. Se garantează că inițial există o cale de la nodul 1 la nodul [$N$]. Să se găsească fluxul maxim care poate fi transportat de la nodul 1 la nodul [$N$].

*Notă:* Această problemă este o continuare a problemelor "MaxFlow":http://www.infoarena.ro/problema/maxflow (Infoarena) și "Mincut":problema/mincut (NerdArena). Datorită numărului mare de muchii, algoritmii Ford-Fulkerson și Edmonds-Karp nu se comportă suficient de bine. Este necesară o implementare a metodei Push-Relabel, algoritmul Relabel-To-Front.
 
Se dă un graf orientat complet cu $N$ noduri. Fiecare muchie are atașată o capacitate naturală (care poate fi 0). Să se găsească fluxul maxim care poate fi transportat de la nodul 1 la nodul [$N$].

h2. Date de intrare

* $1 ≤ N ≤ 800$
* 0 ≤ $c[i][j] ≤ 100.000$

* $c[i][ 1] = $c[N][i] = $c[i][i] = 0$ pentru $i = 1, 2, ..., N$

* $c[i][ 1] = c[N][i] = c[i][i] = 0$ pentru $i = 1, 2, ..., N$

h2. Exemplu

table(example).

table(example).

|_. push-relabel.in |_. push-relabel.out |
| 4
0 3 5 0