Fişierul intrare/ieşire:push-relabel.in, push-relabel.outSursăad-hoc
AutorclasicaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

push-relabel.inpush-relabel.out
4
0 3 5 0
0 0 0 6
0 3 0 4
0 0 0 0
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici