karb

Karb

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

Poveste şi cerinţă...

Se dă un graf neorientat conex cu $N$ noduri şi $M$ muchii. Muchiile au costul $0$ sau $1$. Se cere să se determine un arbore de acoperire de cost exact $K$.

h2. Date de intrare

Fişierul de intrare $karb.in$ ...

Fişierul de intrare $karb.in$ conţine pe prima lini valorile lui $N$, respectiv $M$. Pe următoarele $M$ linii se vor afla câte trei numere $x y w$, separate printr-un spaţiu, reprezentând muchia $(x, y)$ de cost $w$.

h2. Date de ieşire

În fişierul de ieşire $karb.out$ ...

În fişierul de ieşire $karb.out$ se vor scrie $N - 1$ muchii din cele $M$, reprezentând muchiile unui arbore de acoperire de cost $K$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$.
* $1 ≤ M ≤ 200 000$.
* Întotdeauna va exista soluţie.

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

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

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

|
h3. Explicaţie