Se considera un arbore
având costuri atasate pe muchii si un sir de numere naturale. Sa se adauge arborelui
un numar maxim de muchii având costuri dintre numerele date, astfel încât graful
obtinut sa aiba ca arbore partial de cost minim arborele initial.
Date
de intrare
Pe prima
linie a fisierului text apm.in
se afla numarul natural n reprezentând
numarul nodurilor din arbore. Pe urmatoarele n-1
linii se gasesc câte trei numere naturale separate prin cate un spatiu, sub
forma i j c, având semnificatia:
exista muchie de la i la j
avand costul c. Pe
urmatoarele linii se afla sirul de numere dat, câte un numar pe o linie.
Date de iesire
Pe fiecare
linie a fisierului de iesire apm.out
se vor scrie cate trei numere i j c,
având semnificatia: "adaugam o muchie între nodurile i
si j avand costul c".
Cele trei numere se vor separa prin câte un spatiu.
Restrictii si precizari
0<n<256
Costurile muchiilor arborelui
sunt numere naturale nenule <=32000
In sirul de numere dat exista
cel mult 32000 de valori (numere naturale nenule <=30000).
Fiecare element
din sir poate reprezenta costul unei singure muchii adaugate.
Elementele
sirului nu sunt neaparat distincte.
Între oricare
doua noduri din graf va exista cel mult o muchie.
În cazul
în care nu se poate adauga nici o muchie, în fisierul de iesire se va scrie
o singura linie ce va contine valoarea 0.
În graful obtinut dupa
adaugarea muchiilor pot exista mai multi arbori partiali de cost minim, dar
costul acestora trebuie sa fie identic cu al arborelui initial.
În cazul
în care problema admite mai multe solutii, în fisierul de iesire se va scrie
una singura.
Exemplu
apm.in
apm.out
4
1 2 2
3 4 4
3 1 2
2
5
3
1 4 5
2 3 3
Prof.
Dana Lica
Colegiul
Naţional "I.L. Caragiale" Ploieşti
Contact:
danal182001@yahoo.com