@Nizamovoff

Нужны ли алгоритмы с графами в региональном этапе по программированию?

Именно не BFS и DFS, которые работают за O(n+m) и дерево отрезков O(mlogn), а алгоритмы Дейкстры, Форда Беллмана, Флойда (n^2+m, n^2, n^3 соответвенно). Ведь ограничения по вершинам на региональном этапе составляют как правило 10^5 и даже на плюсах такое решение поймает TLE. Может есть их хитрые реализации, по типу НВП за nlogn? Буду благодарен ответам
  • Вопрос задан
  • 127 просмотров
Решения вопроса 1
wataru
@wataru
Да, могут быть нужны. Про то, что ограничения порядка 10^5 - это не факт. Может быть и задача, где ограничения меньше, а решение сложнее.

Потом, еще важные алгоритмы - максимальное паросочетание, максимальный поток и максимальный поток минимальной стоимости (в порядке увеличения сложности и уменьшения частоты).

Далее, что за дерево отрезков на графе?! А еще дейкстра может быть написан за (n+m)logn. И форд-беллман работает за nm, а не n^2.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
gbg
@gbg
Баянист. Тамада. Услуги.
Вы рассуждаете неверным образом.

Олимпиада - это конкурс по поиску талантов, а не стандартный экзамен по критериям. Если на олимпиаде появится задача, решить которую можно чуть красивее при помощи этих алгоритмов и там же будет участник, который эти алгоритмы знает, вы обломаетесь.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
AGIMA Москва
от 150 000 до 250 000 ₽
JUG Ru Group Санкт-Петербург
от 200 000 ₽
СофтТелематика Москва
от 200 000 до 250 000 ₽
21 сент. 2020, в 00:07
10000 руб./за проект
20 сент. 2020, в 23:49
10000 руб./за проект
20 сент. 2020, в 23:44
20000 руб./за проект