|
Titlul: Descompunere in componente conexe Scris de: Costinnel din Iunie 04, 2012, 15:05:16 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 :oops: . De fapt , problema e aceasta : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=960 Imi puteti da indicatii mai eficiente? Titlul: Răspuns: Descompunere in componente conexe Scris de: Sorin Rita din Iunie 04, 2012, 17:33:55 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.
|