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

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

*Notă:* Această problemă este o continuare a problemelor "MaxFlow":http://www.infoarena.ro/problema/maxflow (Infoarena) și "Mincut":http://varena.ro/problema/mincut (Varena). 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.

*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. Exemplu

table(example).

table(example).

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