Максимальный поток, поток с ограничениями, поток минимальной стоимости, паросочетания, мин. разрез и т д.
Никак немогу найти задач на эти темы. Точнее никак не получается в задачах этого увидеть. Покидайте пожалуйста, кому не сложно ссылки на задачи (например с того же тимуса) на эти темы.
А то все примеры, какие я видел - так это "симпатичные таблицы")
Спасибо всем, интересные задачи, если еще что-то "необычное" с виду никак не напоминающее потоки будет, скиньте сюда если не сложно. Один маленький вопрос есть: в некоторых задачах с виду ограничения такие, что решение за O(n^3) не должно проходить, тем не менее все ок. Это связано с тем, что в этих задачах "хорошая" сеть получается?
К разным задачам нужно применять оптимальный алгоритм. Где-то нужен Диница за О(V^2*E), где-то Форда-Фалкерсона за O(V^2 * FLOW), где-то Эдмондса-Карпа за O(min( V*E^2, E*FLOW )). Например, в задаче 1721 на тимусе оптимально писать алгоритм Куна (нахождение максимального паросочетания за O(V*E)) - сведение задачи к потокам не пройдет у меня не прошло
сведение задачи к потокам конечно же должно пройти, ведь Алгоритм Диница на графе для поиска максимального паросочетания, будет работать за O(E * Sqrt(V)), этот алгоритм поиска максимального паросочетания также известен как алгоритм Хопкрофта-Карпа.
http://acm.timus.ru/problem.aspx?space=1&num=1076
http://acm.timus.ru/problem.aspx?space=1&num=1109
http://acm.timus.ru/problem.aspx?space=1&num=1237
http://acm.timus.ru/problem.aspx?space=1&num=1277
http://acm.timus.ru/problem.aspx?space=1&num=1421
http://acm.timus.ru/problem.aspx?space=1&num=1721
не пройдету меня не прошлоЗадача A "Поедание сыра"