328 Ro

[•azotlichid]

Aici puteţi discuta despre problema Ro.

[•feelshift]

Îmi poate da cineva un hint la problema asta?
Ce am încercat până acum: Cât timp există puncte de articulație, calculez pentru fiecare diferența dintre suma costurilor vecinilor și costul său. Aleg dintre acestea nodul cu cea mai mare valoare și îl promovez la rangul de capitală europeană, eliminându-l din graf și identificând din nou punctele de articulație. Apoi, pentru fiecare componentă conexă aplic același procedeu până când toate nodurile sunt izolate.

[•wefgef]

E foarte important faptul ca orice componenta biconexa are cel mult 13 noduri. Incearca sa te folosesti de asta facand arborele componentelor biconexe si al nodurilor critice.