ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    31 Mar 2002  13:56:48
 To : Sergey Politov
 Subject : UOI2001
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  Sergey!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
  Эй, уважаемые Sergey Politov и Alexander Shmidt! Что за "Re: UOI2001", а где же
 яйца?!
 
  AS>> Hе, не хуже. Сразу массивами кидаем данные: при проходе - из
  AS>> текущего массива в "кэш", при проверках - из "кэша" в текущий.
  SP>   А размер массива ни от количества вершин, ни от количества ребер не
  SP> зависит?
 
 Ограничение - 100 вершин. В память помещается. Массивы кидаем целиком (вне
 зависимости от n).
 
 Хотя, это уже неважно - решение найдено: при построении мин. дерева надо для
 каждой пары (i,j) хранить длину максимальной дуги из тех, которые получились на 
 пути от i до j вершины (1<=i,j<=n) (пусть, в массиве MD). Пусть длина
 полученного мин. дерева =minlen.
 Тогда находим минимум из ( minlen-D[i,j]+MD[i,j] )
 где i и j такие, что ребро (i,j) не принадлежит минимальному дереву.
 Этот минимум, очевидно, будет вторым лучшим решением.
 
 Good bye, mister Politov                        _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                  _/
 ... ...и не дай Вам Бог в наше тяжелое время родиться пенсионером... (с)KBH
 --- А у твоего ГолДеда стоит... фильтрация мессаг???
  * 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