@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
Баянист. Тамада. Услуги.
Вы рассуждаете неверным образом.

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

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

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