Diferențe pentru problema/mincut între reviziile #2 si #8

== include(page="template/taskheader" task_id="mincut") ==

Poveste și cerință...

*Notă:* Aceasta este o continuare a problemei "Maxflow":http://www.infoarena.ro/problema/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$].

h2. Date de intrare

Fișierul de intrare $mincut.in$ ...

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$].

h2. Date de ieșire

În fișierul de ieșire $mincut.out$ ...

Î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ă.

h2. 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ă.

h2. Exemplu
table(example).
|_. mincut.in |_. mincut.out |

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

| 4 5
1 2 3
1 3 5
2 4 6
3 4 4
3 2 3
| 8
1 3
1 2

|

h3. Explicație
 
...
 

== include(page="template/taskfooter" task_id="mincut") ==