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

Question

[Айнур Низамов]

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

Answer 1

[Wataru]

Да, могут быть нужны. Про то, что ограничения порядка 10^5 - это не факт. Может быть и задача, где ограничения меньше, а решение сложнее.

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

Далее, что за дерево отрезков на графе?! А еще дейкстра может быть написан за (n+m)logn. И форд-беллман работает за nm, а не n^2.

Comments

[Wataru]

Bavashi, как раз mn и есть самая точная оценка, ибо m может быть порядка n^2. Т.е. Форд-Беллман будет n^2 на сильно разряженном графе и n^3 на плотном.

[Айнур Низамов]

wataru, все равно будет тест с плотным графом, то бишь облом решения. n^2 - это еще в лучших случаях

[Айнур Низамов]

wataru, ограничения для графов всегда 10^5 - это уже традиция. Дабы решение на Java за nlogn не ловило TLE

[Wataru]

Nizamovoff, Вообще без разницы, какие будут тесты. Сложность Форда-Беллмана O(nm) в общем случае.

> ограничения для графов всегда 10^5 - это уже традиция

Это вы себе сами придумали. Если авторы подразумевают какой-нибудь мин-кост-макс-флоу, например, то 10^5 в ограничениях не поставят.

Answer 2

[Армянское Радио]

Вы рассуждаете неверным образом.

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

Comments

[Айнур Низамов]

Но прикол в том, что решив задачу за n^2 с ограничениями n^5, мы получим n^5^2 = n^10. Плюсы за секунду успевают сделать 10^8 итераций в секунду, а ограничения по времени, как правило, составляет 1 секунду, реже - 2. Решение получит TLE - как вследствие алгоритм - бесполезен. Вот так я думаю