Fişierul intrare/ieşire:karb.in, karb.outSursăAlgoritmiada 2010, Runda 3
AutorMarius StroeAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.175 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Karb

Se dă un graf neorientat simplu 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.

Date de intrare

Fişierul de intrare karb.in conţine pe prima lini valorile lui N, M, respectiv K. 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.

Date de ieşire

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

Restricţii

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

Exemplu

karb.inkarb.out
6 8 3
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content