infoarena

Am primit la locală o problemă destul de dubioasă de care nu am prea reușit să mă prind. Ea sună cam așa: Fiind dat un graf neorientat conex, cu N noduri (N <= 200) și M muchii, determinați numărul minim de muchii care trebuiesc adăugate astfel încât graful să admită ciclu eulerian, știind că muchiile nu se pot dubla (dacă există muchie de la x la y, nu mai pot adăuga încă una de la x la y).

Pai trebuie sa adaugi muchii pana ce toate gradele nodurilor sunt pare. Cuplezi noduri de grad impar

Cum graful este deja conex, intr-adevar raspunsul este numarul de noduri de grad impar / 2. Poti cupla oricum nodurile de grad impar.

Tocmai asta e distracția, că există posibilitatea ca unele muchii de grad impar să fie cuplate între ele, deci trebuiesc găsite alte modalități de a le cupla.

Exista un numar par de noduri cu grad impar (rezultat cunoscut!) Incercam sa cuplam noduri de grad impar. Daca nu putem, luam un nod de grad par si il cuplam cu cate doua noduri de grad impar. Nodul de grad par ramane par (am adunat 2 la grad), iar cele doua noduri de grad impar au devenit pare.

Problema este intr-adevar dubioasa. Ce te faci la un graf complet cu numar par de noduri? Nu ai solutie.

În cazul în care nu ai soluție afișezi -1.
M-am uitat pe sursa oficială și este cam bulăneală, adică nu mi-a luat mult să găsesc un contraexmplu. I-am semnalat autorului și acum om vedea.

Solutia data de Narcis Parfene este in mod evident, gresita. Contraexemplu:


Nodurile 1, 2, 3, 4, 5, 6 au gradul impar (=3), iar nodurile 7 si 8 au grad par (=6).

Algoritmul de care vorbeam poate sa cupleze 1 cu 3 si 2 cu 4, blocandu-se la nodurile 5 si 6 deoarce: exista muchie de la ele la toate nodurile de grad par si nu mai exista alte noduri cu grad impar necuplate.

Exista solutia: 1 cu 3, 4 cu 6, 5 cu 2.

Implicatia cuplaj pe graf general => problema aceasta este evidenta. Implicatia inversa este mai greu de demonstrat. Ma chinui si daca iese ceva revin cu update.

Am căutat puțin pe internet și problema nu pare să admită soluție polinomială. Se pare că județul nostru e "blestemat". Acum doi ani la județeană s-a întâmplat ceva oarecum asemănător. :D

   Si eu m-am intalnit cu aceeasi problema la locala si am facut-o in felu urmator : am unit cat am putut nodurile cu grad impar , iar cand nu am mai putut sa unesc am luat cate doua noduri de grad impar si am dus muchie intre fiecare si un nod cu grad par(evindent intre care nu exita muchie deja), problema cerea sa aflu si un ciclu eulerian din nodul 1 asta era simplu.
   Dupa doua ore de implementat si testat am gasit si eu test care nu afisa solutia optima si mi-am pus semne de intrebare pana cand s-a terminat timpu si uite asa n-am avut timp de problema a doua  :annoyed:.

Intr-adevar, solutia data de mine e rea, dar enuntul pare ca nu cere muchiile care se adauga, ci doar numarul lor. Totusi poate aflam enuntul precis. E pe undeva pe net de descarcat?

   Enunţul cerea numarul minim de muchi si muchiile pe care trebuie sa le adaugi astfel incat graful obţinut sa fie eulerian , iar dupa ce ai gasit muchiile sa afişezi un ciclu eulerian care incepe cu nodul 1.
   Pe net nu se găsesc inca pentru ca abia azi a avut loc olimpiada.

Se cere atât numărul de muchii, cât și muchiile efective, cât și ciclul eulerian al grafului format din muchiile date și muchiile adăugate. Dar algoritmul descris de tine tot pică (sursa oficială face ceva asemănător), chiar dacă s-ar cere doar numărul de muchii. :)

L.E. Am atașat problema în forma în care ne-a fost dată aici (http://infoarena.ro/utilizator/mishu91?action=download&file=Cartite.doc&safe_only=false).