|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 28 Mar 2002 06:19:55
To : Alexander Shmidt
Subject : Re: UOI2001
--------------------------------------------------------------------------------
До меня дошли слухи, что *26.03.02* *22:23:12* пролетало сообщение
от Alexander к *Sergey Politov* про *"UOI2001"*. И я решил вмешаться.
[...]
AS> Вершин, как обычно, - <=100. Веса ребер <=300 (шоб в integer влезли, надо
AS> полагать; хотя это, имхо, не принципиально)
AS> Есть идея построить "лучший" вариант, а потом покантовать (ребра
AS> поразрезать-подорисовывать).
AS> Или придется по всем ребрам полученного "лучшего" решения пройтись, и,
AS> удаляя ребро, решать задачу заново. После чего сравнить результаты этих
AS> (n-1) проходов.
Вообще я это и хотел предложить только удалив ребро не забывай его вернуть.
AS> Прим-Краскал, если меня не глючит, имеет сложность O(n^3). Тогда конечный
AS> алгоритм будет О(n^4). Что народ скажет?
А вообще Краскал имеет сложность O(ElogE), или оценив E<V^2, O(V^2log(V)), но
лагирифм получается из за сортировки, а тут можно не соритровать по несколько
раз
поэтому сложность получится O(V^3).
np: Manowar - Sting Of The Bumblebee
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Heavy Metal is the Law. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
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 |
|
|
