infoarena

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

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?

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 :).

Gata, m-am prins.  Multumesc. :D (Nu stiam proprietatea, dar mi-a picat fisa ca k e par :) ). Misto problema.  :thumbup:

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...

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 :).