На последнем тестовом раунде (Codeforces Testing Round 5) в качестве сложной задачи была предложена моя задача 267C - Berland Traffic. Задача интересная и, как показали результаты, непростая. Придумал эту задачу я довольно давно, а дал ее (с другим названием и легендой) на школьные летние сборы в Малоярославце (2003 года).
Сегодня испытал забавное ощущение, заметив в контесте Варшавского университета Петрозаводских зимних сборов 2012 задачу "I. Uniform Flow". Глянул тесты — и тесты мои :-) Забавный круг совершила эта задача!
P.S. Кстати, задачу эту я считаю довольно полезной. Полагаю, схожие идеи иногда могут встретиться и в других задачах.
А можно услышать её разбор?
Как ни странно, к потоку эта задача не имеет вообще никакого отношения.
Раз для любой пары городов сумма потоков не меняется, значит, в частности, это верно для истока и любой вершины. Введём понятие "потенциал вершины" — эта сумма потоков от истока до вершины. После этого очевидно вычисляется мощность потока и поток по каждому ребру. Теперь у нас есть n - 1 переменная, n - 2 условия (сохранение потока). Гауссом выразим все потенциалы через какой-то. Теперь есть 2m линейных неравенств (по два на ребро — в каждую сторону). Надо максимизировать линейную функцию от одной переменной (поток) в заданных ограничениях — пересекаем все ограничения и проверяем граничные точки.
А какая оценка на число граничных точек?
Ограничения все линейны. Пересечение отрезков — отрезок. Две.