1

(2 ответов, оставленных в Algo)

Все, что Вы сказали, по-моему мнению, верно.

Замечания:
vector<int> example; // резиновый массив, изначально нулевого размера.
vector<int> g[MAXN]; // обычный массив "массивов нулевого размера"

Пример чтения графа из файла (часто встречающийся вариант):

int vertices, edges;
scanf("%d%d", &vertices, &edges);
for (int ei = 0; ei < edges; ++ei)
{
  int a, b;
  scanf("%d%d", &a, &b);
  a--, b--;

  // в список смежности вершины "a" добавляем вершину "b".
  // Это соответствует добавлению в конец резинового массива g[a] нового элемента.
  g[a].push_back(b);

  // симметрично для g[b]
  g[b].push_back(a);
}

У меня незначительные замечания:
1) Есть чуть более простая жадность для одномерного случая (у меня она работает чуть быстрее):

int sum = 0, ans = a[0];
for (int i = 0; i < n; ++i)
{
  sum += a[i];
  ans = max(ans, sum);
  if (sum < 0)
    sum = 0;
}

Кстати это называется алгоритм Kadane, а n^2*m алгоритмом Bentley
(есть ссылка в Takaoka 2002)

Интересно, что gcc строку ans = max(ans, sum); оптимизирует на ура (т.е. вручную улучшить не удалось),
и самое долгое место это if (sum < 0) (проверка бита знака числа).

2) В той же статье Takaoka двумерная задача сводится к задаче APSP (всех пар кратчайших путей во взвешенном графе). Т.е. они асимптотически эквивалентны.
Но с 2002 года только сам Takaoka улучшил оценку 2 раза, а всего она менялась не менее 7 раз и лучшая из того, что я знаю:
T. Chan 2007: n^3 * log^3 log n / log^2 n.

3) Когда мне пришлось реализовывать этот алгоритм (строго говоря предыдущий 2006-ого года), я попытался сравнить его константу с Флойдом. Что-то у меня получалось, даже при самых грубых оценках, что он начнет обгонять Флойда при n >= 2^50.
Сложно себе представить запуск Флойда при таких ограничениях, даже при самых оптимистичных прогнозах на развитие процессоров ((

4) Важным же замечанием является то, что открытым и наиболее интересным является вопрос о решении APSP за время n^(3 - eps). Для любого малой константы eps.

5) Ахо и Ульман показали, что вычисление APSP эквивалентно одному умножению матриц в тропической полугруппе
(вместо сложения - min, вместо умножения - арифметическое сложение). Когда хотят улучшить оценку, эту задачу все и решают, а не все выше означенные.

Ссылка на статью: http://www.cs.uwaterloo.ca/~tmchan/moreapsp.pdf

3

(8 ответов, оставленных в Algo)

Здравствуйте, это я натравил Сережу на вашего Краскала )

Насколько я понимаю, в основной статье про СНМ реализация тоже m*log(n), а не заявленная про Аккерманна.
Т.к:
1. В первой реализации, там вместо размеров оцениваются высоты. Может я не прав, но, по-моему, это не дает требуемую оценку.
2. Про вторую (рандомизированную) написал Сережа.