|
Titlul: 974 Karb Scris de: Paul-Dan Baltescu din Februarie 21, 2010, 13:43:01 Aici puteti discuta despre problema Karb (http://infoarena.ro/problema/karb).
Titlul: Răspuns: 974 Karb Scris de: Moise Razvan din Februarie 21, 2010, 22:42:14 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?
Titlul: Răspuns: 974 Karb Scris de: Paul-Dan Baltescu din Februarie 22, 2010, 00:08:15 Inseamna ca mai trebuie sa te pui la curent cu notiunile, algoritmii, etc. Au fost elevi (http://infoarena.ro/monitor?task=karb&score_begin=100)de clasele 9-10 care au rezolvat problema in concurs.
Titlul: Răspuns: 974 Karb Scris de: Adrian Budau din Februarie 23, 2010, 21:51:36 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! :D |