Diferențe pentru problema/mincut între reviziile #3 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)
* Ca urmare, costul maxim al unui arc este 220.000

* 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
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") ==