375 Colorare2

[•azotlichid]

Aici puteţi discuta despre problema Colorare2.

[•pauldb]

Se poate face ceva mai destept la problema asta decat cuplaje maxime pana cand acoperi toate muchiile?

[•azotlichid]

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 

[•devilkind]

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

[•pauldb]

Nu e corecta. Am gasit contraexemplu:

Cod:

5 4 12
1 6
2 6
2 7
2 8
3 7
3 9
4 6
4 8
4 9
5 7
5 8
5 9

[Se poate colora in 3 culori]
Dar eu implementand chestia aia am luat 75 de puncte. Deci probabil ai gresit si implementarea.

[•devilkind]

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
3
2
3
1
2
1
1
3
2
1
2
3

Numai 3 culori

[•astronomy]

Aici e demonstratia: www.misojiro.t.u-tokyo.ac.jp/~iwata/dmi/dmi01e.pdf