ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    26 Mar 2002  23:23:12
 To : Sergey Politov
 Subject : UOI2001
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  Sergey!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
  Эй, уважаемые Sergey Politov и Alexander Shmidt! Что за "Re: UOI2001", а где же
 яйца?!
 
  AS>> (hint тем, кто не понял прикола: для нахождения остовного дерева
  AS>> мин. длины есть алгоритм Прима-Краскала, простой до неприличия; а
  AS>> нужно - кроме мин. дерева найти еще одно, "второе" по
  AS>> минимальности, как Вам такое? :)   )
  SP> А ограничения какие?
 
 Вершин, как обычно, - <=100.
 Веса ребер <=300 (шоб в integer влезли, надо полагать; хотя это, имхо, не
 принципиально)
 
 Есть идея построить "лучший" вариант, а потом покантовать (ребра
 поразрезать-подорисовывать).
 Или придется по всем ребрам полученного "лучшего" решения пройтись, и, удаляя
 ребро, решать задачу заново. После чего сравнить результаты этих (n-1) проходов.
 
 Прим-Краскал, если меня не глючит, имеет сложность O(n^3).
 Тогда конечный алгоритм будет О(n^4). Что народ скажет?
 
 Good bye, mister Politov                        _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                  _/
 ... Ешь ананасы, рябчиков жуй - сегодня ведь твой день рожденья, буржуй!
 --- А у твоего ГолДеда стоит... фильтрация мессаг???
  * Origin: Без модема и ФИДЫ - ни туды и ни сюды!
  (2:464/34.74)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    UOI2001   Alexander Shmidt   24 Mar 2002 01:35:56   Re: UOI2001   Sergey Politov   26 Mar 2002 06:36:10   UOI2001   Alexander Shmidt   26 Mar 2002 23:23:12   Re: UOI2001   Sergey Politov   28 Mar 2002 06:19:55   UOI2001   Alexander Shmidt   28 Mar 2002 23:34:40   Re: UOI2001   Sergey Politov   29 Mar 2002 06:21:58   UOI2001   Alexander Shmidt   29 Mar 2002 23:22:00   Re: UOI2001   Sergey Politov   31 Mar 2002 04:40:41   UOI2001   Alexander Shmidt   31 Mar 2002 13:56:48