|
Titlul: 375 Colorare2 Scris de: Adrian Vladu din Martie 22, 2007, 00:16:13 Aici puteţi discuta despre problema Colorare2 (http://infoarena.ro/problema/colorare2).
Titlul: Răspuns: 375 Colorare2 Scris de: Paul-Dan Baltescu din Martie 28, 2007, 12:25:53 Se poate face ceva mai destept la problema asta decat cuplaje maxime pana cand acoperi toate muchiile?
Titlul: Răspuns: 375 Colorare2 Scris de: Adrian Vladu din Martie 28, 2007, 12:29:19 da :) gandeste-te intai la o margine inferioara pt numarul de culori cu care ai putea colora muchiile grafului si apoi incearca sa verifici daca asta nu este cumva o margine foarte stransa :-'
Titlul: Răspuns: 375 Colorare2 Scris de: Savin Tiberiu din Martie 28, 2007, 13:12:24 Citat Se poate face ceva mai destept la problema asta decat cuplaje maxime pana cand acoperi toate muchiile? Initial si eu am avut exact aceeasi idee ca si tine, dar am luat numai 5 pct cu ea :(. Este o metoda corecta si am gresit eu implmenetarea sau nu??Titlul: Răspuns: 375 Colorare2 Scris de: Paul-Dan Baltescu din Martie 28, 2007, 19:33:58 Nu e corecta. Am gasit contraexemplu:
Cod: 5 4 12 Dar eu implementand chestia aia am luat 75 de puncte. Deci probabil ai gresit si implementarea. :) Titlul: Răspuns: 375 Colorare2 Scris de: Savin Tiberiu din Martie 28, 2007, 21:16:37 mda si eu ma gandeam ca nu e corecta ptr ca nu prea reuseam sa demonstre nici macar intuitiv corectitudinea. Oricum pe testul pus de tine programul meu a dat urmatoarea solutie:
Cod: 3 Titlul: Răspuns: 375 Colorare2 Scris de: Airinei Adrian din Martie 28, 2007, 21:33:00 Aici e demonstratia: www.misojiro.t.u-tokyo.ac.jp/~iwata/dmi/dmi01e.pdf
|