Нужны ли алгоритмы с графами в региональном этапе по программированию?
Именно не BFS и DFS, которые работают за O(n+m) и дерево отрезков O(mlogn), а алгоритмы Дейкстры, Форда Беллмана, Флойда (n^2+m, n^2, n^3 соответвенно). Ведь ограничения по вершинам на региональном этапе составляют как правило 10^5 и даже на плюсах такое решение поймает TLE. Может есть их хитрые реализации, по типу НВП за nlogn? Буду благодарен ответам
Да, могут быть нужны. Про то, что ограничения порядка 10^5 - это не факт. Может быть и задача, где ограничения меньше, а решение сложнее.
Потом, еще важные алгоритмы - максимальное паросочетание, максимальный поток и максимальный поток минимальной стоимости (в порядке увеличения сложности и уменьшения частоты).
Далее, что за дерево отрезков на графе?! А еще дейкстра может быть написан за (n+m)logn. И форд-беллман работает за nm, а не n^2.
Bavashi, как раз mn и есть самая точная оценка, ибо m может быть порядка n^2. Т.е. Форд-Беллман будет n^2 на сильно разряженном графе и n^3 на плотном.
Олимпиада - это конкурс по поиску талантов, а не стандартный экзамен по критериям. Если на олимпиаде появится задача, решить которую можно чуть красивее при помощи этих алгоритмов и там же будет участник, который эти алгоритмы знает, вы обломаетесь.
Но прикол в том, что решив задачу за n^2 с ограничениями n^5, мы получим n^5^2 = n^10. Плюсы за секунду успевают сделать 10^8 итераций в секунду, а ограничения по времени, как правило, составляет 1 секунду, реже - 2. Решение получит TLE - как вследствие алгоритм - бесполезен. Вот так я думаю
