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

push-relabel

Push-Relabel (clasele 11-12)

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

Poveste și cerință...

*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

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

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

h2. Date de ieșire

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

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

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 |

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

| 4
0 3 5 0
0 0 0 6
0 3 0 4
0 0 0 0
| 8

|

h3. Explicație
 
...
 

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