Задать вопрос
Lite_stream
@Lite_stream

Можно ли обойтись без бин. поиска?

Дан неориентированный граф. Требуется ориентировать каждое ребро так, чтобы максимальная исходящая степень была минимальна.
За O(g(n) * logn)
За O(g(n))
Где g(n) скорость работы алгоритма max flow

Ума не приложу, как здесь можно просто за g(n) решить, вот довольно естественное решение за g(n) * logn, с юинпоиском по величине X рёбер S->vi - с раздвоение рёбер исходного G. (рёбра s->vi и vij->t рисовать не стал, думаю и так понятно что имеется в виду). Пропускная способность зелёных - бинпоиск, фиол. - 1, чёрных - 1, условие бин поиска - flow = (Σdeg/2)
675f0a9f3d7e7098175219.png
  • Вопрос задан
  • 84 просмотра
Подписаться 2 Простой Комментировать
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Именно max flow, а не mincostmaxflow? Потому что есть очевидное решение с mincostmaxflow.

Граф почти такой же. Раздвоенное ребро. В середину каждого ребра вход из истока пропускной способностью 1 и стоимостью 0. Вдоль ребра в обе стороны такие же ребра - пропускной способности 1 и стоимости 0. Из вершины делаем degree(v) ребер в сток. Каждое пропускной способностью 1 и прогрессивно увеличивающимися стоимостями. Первые ребра стоимостью 1. Вторые - n+1, сделующие (n+1)^2 и т.д.

Стоимость полного потока будет тем меньше, чем меньше максимальная степень, ведь даже одно ребро стоимостью (n+1)^k для вершины степени k+1 хуже чем если бы все вершины имели степень k и ответ был бы n*(n+1)^(k-1).

Если нужен именно просто поток, а не минимальной стоимости, то возможно можно изменить алгоритм потока, чтобы искать его итеративно для всех возможных значений x в вашем графе. Ведь алгоритм итерационно ищет дополняющий путь в остаточной сети. И ответ для x можно использовать в качестве стартового потока для задачи с x+1. Т.е не надо логарифм раз запускать поток для разных графов, а после выполнения увеличить пропускные сопособности нужных ребер на 1 и запустить поток дальше. Это будет как если бы вы запустили поток один раз с максимальной пропускной способностью сразу.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы