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)

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.

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