Fișierul intrare/ieșire	push-relabel.in, push-relabel.out	Sursă	ad-hoc
Autor	clasică	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.15 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Push-Relabel (clasele 11-12)

Notă: Această problemă este o continuare a problemelor MaxFlow (Infoarena) și Mincut (Varena). Datorită numărului mare de muchii, algoritmii Ford-Fulkerson și Edmonds-Karp nu se mai 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.

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

Date de ieșire

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

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

Exemplu