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

== 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":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$].

Poveste și cerință...

h2. Date de intrare

Fișierul de intrare $push-relabel.in$ conține pe prima linie numărul [$N$]. Pe următoarele $N$ linii apar câte $N$ numere. Al [$j$]-lea număr de pe linia $i$ reprezintă capacitatea muchiei $(i, j)$.

Fișierul de intrare $push-relabel.in$ ...

h2. Date de ieșire

În fișierul de ieșire $push-relabel.out$ se va tipări un singur număr, valoarea fluxului maxim.

În fișierul de ieșire $push-relabel.out$ ...

h2. Restricții

* $1 ≤ N ≤ 800$
* 0 ≤ $c[i][j] ≤ 100.000$
* $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
0 0 0 6
0 3 0 4
0 0 0 0
| 8

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

|

h3. Explicație
 
...
 

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