Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 286 Ancient Decoration  (Citit de 12496 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« : Iulie 15, 2007, 12:09:41 »

Initial am crezut ca e un algoritm cunoscut, dar apoi mi-am dat seama ca am inteles gresit enuntul. Insa tot nu ma prind cum se face.

Problema se gaseste aici: http://acm.sgu.ru/problem.php?contest=0&problem=286
« Ultima modificare: Iulie 15, 2007, 19:10:58 de către Paul-Dan Baltescu » Memorat

Am zis Mr. Green
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #1 : Iulie 15, 2007, 12:19:10 »

Hint#1: Gandeste-te la un graf bipartit in care ambele multimi ale sale contin toate nodurile din graful din enunt (stiu, e mai dubios). Ce semnifica un cuplaj maximal in graful acesta?
Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #2 : Iulie 15, 2007, 17:32:48 »

Ca sa intelegi la ce iti foloseste hintul lui silviu, ar trebui sa stii de nuj ce proprietate dubioasa de care ne vorbea mircea, conform careia intr-un graf bipartit regulat ai cuplaj maximal. In cazul de fata asta inseamna ca daca ai n noduri in stanga, n in dreapta, alea din stanga si din dreapta au acelasi grad, atunci vei reusi sa cuplezi toate nodurile.

P.S. : Cam tare problema asta Smile.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #3 : Iulie 15, 2007, 17:53:21 »

Gata, m-am prins.  Multumesc. Very Happy (Nu stiam proprietatea, dar mi-a picat fisa ca k e par Smile ). Misto problema.  Thumb up
Memorat

Am zis Mr. Green
mariusdrg
Client obisnuit
**

Karma: 70
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #4 : August 22, 2008, 12:18:57 »

Deci eu ce am facut suna ceva in genu... dublez toate nodurile pun toate muchiile si de la a la b si de la b la a, fac un cuplaj pe acolo... ala o sa imi dea niste cicluri si colorez dupa ciclurile respective.... dar am o problema.. daca pun muchiile si  b -> a si a -> b mi se tot adauga aceeasi muchie de mai multe ori in solutie... As vrea un hint despre cum pot sa rezolv chestiile astea(am incercat 3 euristici, una puneam muchii din stanga la dreapta doar daca nodul din stanga e mai mic decat ala din dreapta, incercam sa fac ca gradurile din stanga sa semene cat mai mult cu cele din dreapta cu un fel de greedy, si am mai incercat sa formez niste cicluri si componente biconexe inainte sa le bag in graful bipartit,dar fara prea mare succes) ... Daca cineva imi poate spune ce gresesc.. Multumesc!
P.s. Nu prea am inteles hintul ala a lu silviu .... Daca nu sunt pe solutie ziceti doar ca nu sunt pe solutie...
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #5 : August 22, 2008, 12:23:55 »

E bine sa dublezi nodurile si sa faci cuplaj, iar apoi sa colorezi muchiile din cuplaj.

E rau sa pui muchie de la a->b si de la b->a, pentru ca asa cum ai zis si tu poate aparea o muchie de mai multe ori in solutie. Pentru fiecare muchie, va trebui sa ii gasesti o singura orientare si sa o bagi in graful bipartit. Daca reusesti sa orientezi muchiile astfel incat pentru fiecare nod x, exact jumate din muchiile sale incidente sunt orientate dinspre/inspre x, vei avea un cuplaj maximal => solutie. Te las pe tine sa te gandesti cum faci orientarea... ar trebui sa fie destul de usor Smile.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines