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

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

Vezi soluțiile trimise | Statistici

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