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

Vezi solutiile trimise

Mincut (clasele 11-12)

Notă: Aceasta este o continuare a problemei Maxflow de la Infoarena, compatibilă pe intrare/ieşire, cu modificările:

  • Am modificat testele pentru a transforma multigrafurile în grafuri (am însumat muchiile între aceleaşi noduri).
  • Ca urmare, costul maxim al unui arc este 220.000.
  • Am redus memoria, pentru a impune o implementare în spaţiu O(M + N).

Se dă un graf orientat cu N noduri şi M muchii. 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ă o mulţime de muchii cu capacitatea totală minimă după a căror eliminare să nu mai existe o cale de la nodul 1 la nodul N.

Date de intrare

Fişierul de intrare mincut.in conţine pe prima linie 2 numere, N si M, reprezentând numărul de noduri şi numărul de muchii din graf. Pe fiecare din următoarele M linii se vor afla câte 3 numere naturale, x, y si z, cu semnificaţia că există o muchie de la nodul x la nodul y de capacitate z.

Date de ieşire

În fişierul de ieşire mincut.out se va afişa pe prima linie un singur număr F, reprezentând capacitatea totală minimă a muchiilor eliminate. Pe următoarele linii se vor afişa perechi de numere x y cu semnificaţia că muchia x y este eliminată.

Restricţii

  • 2 ≤ N ≤ 1.000
  • 1 ≤ M ≤ 5.000
  • Capacităţile muchiilor sunt numere naturale în intervalul [1, 220.000].
  • Între oricare două noduri x şi y există maxim o muchie, însă muchiile x → y şi y → x pot exista simultan.
  • Nu există muchii de la un nod la el însuşi.
  • Dacă există mai multe soluţii, oricare este acceptabilă.

Exemplu

mincut.inmincut.out
4 5
1 2 3
1 3 5
2 4 6
3 4 4
3 2 3
8
1 3
1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici