Descompunere in componente conexe

[•costi_.-.]

Salut.
Dandu-se un graf neorientat,ponderat,conex ,cum il putem descompune in K componente conexe astfel incat suma muchiilor eliminate sa fie maxima?
Solutia mea burta implica generarea submultimilor de muchii, eliminarea rand pe rand a fiecarei submultimi din graf si verificarea conexitatii.Dar pentru M > 11, rup segmentul de stiva pentru ca se ajung la  cel putin 2048 apeluri  .
De fapt , problema e aceasta : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=960
Imi puteti da indicatii mai eficiente?

[•soriyn]

Poti sa folosesti APM. Adica in loc sa il descompui in K componente conexe cu suma muchiilor maxima il poti descompune in N-K folosind APM iar suma muchiilor neutilizate e numarul cautat de tine.