| Fişierul intrare/ieşire: | karb.in, karb.out | Sursă | Algoritmiada 2010, Runda 3 |
| Autor | Marius Stroe | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | karb.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
remote content
