ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1109. Конференция

Suggestion for TLE 7
Послано Aneta 22 апр 2019 19:53
If you are using Edmonds-Karp, chnage it to regular Ford-Fulkerson (do DFS instead of BFS), because the running time in this case is better that way, as the maximum flow can be 1000 at most, so the complexity will be O(V*|f|) <= 2000*1.000.000 and this umber fits in 0.5 seconds. However, in case of E-K, the worst case running time is O(V^2*E) <= 1.000.000 * 1.000.000, which is the case of 1000-1000 complete graph and this exceeds the given 0.5 seconds.