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

*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 graf (am însumat muchiile între aceleași noduri).

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

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

* $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$ exista maxim o muchie, însă muchiile $x → y$ și $y → x$ pot exista simultan.

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