974 Karb

[•pauldb]

Aici puteti discuta despre problema Karb.

[•Bunicool]

Asta e problema de 9-10? Ca vad ca s-a dat si la studenti si practic nam inteles nimic din textul problemei (sunt a 9-a). Despre ce e vorba?

[•pauldb]

Inseamna ca mai trebuie sa te pui la curent cu notiunile, algoritmii, etc. Au fost elevi de clasele 9-10 care au rezolvat problema in concurs.

[•freak93]

Am o rezolvare diferita de cea oficiala si nu sunt sigur daca e corecta 100%, desi am luat 100 de puncte pe ea.
Fac ceva de genul urmator:
1)Adaug tote muchiile de cost 1 in graf si imi formez un alt graf cu ele, daca intre 2 noduri exista deja un drum marchez o dublare(adica nu as avea nevoie de o astfel de muchie in final).
2)Adaug muchiile de cost 0 si in acest graf si la arborele solutie daca satisfac una din urmatoarele conditii.

I)Daca uneste doua noduri intre care nu exista drum(in graful nou format)
II)Daca uneste doua noduri intre care exista un drum format de muchii de cost 1 si nu exista drum format din muchii de cost 0 si numarul de dublari este mai mic decat (numarul_de_muchii_de_cost_1-K). In acest caz incrementez si numarul de dublari

3)Mai trec odata odata prin muchiile de cost 1 si le adaug in arborele solutie doar daca nu exista un drum intre cele 2 noduri in arborele solutie.

Daca ma puteti lamuri va rog sa-mi raspundeti.
Multumesc anticipat!