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

Question

[floppa322]

Дан неориентированный граф. Требуется ориентировать каждое ребро так, чтобы максимальная исходящая степень была минимальна.
За 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)

Answer 1

[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 и запустить поток дальше. Это будет как если бы вы запустили поток один раз с максимальной пропускной способностью сразу.

Comments

[floppa322]

Спасибо за подробный ответ

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

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

Тут кажись может быть проблема, что надо nlogn бит на число (для веса ребра), хотя для "нормальных" графов 64 бита должно хватить. Полагаю, речь всё-таки про max flow, потому что скорость работы с max flow (для самого быстрого алгоритма) должна быть (E*V)*logV, а для min cost вроде E*E*logV+E*V*log^2(V)

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

Я так понял, речь идёт именно про алгоритм Форда-Фалкерсона ? Здесь же ФФ будет только по 1-му потока прибавлять, поэтому бинарным поиском не получится, придётся линейным. Если использовать ФФ с линейным поиском, то должно быть O(Ans * E) = O(V * E), ну да, лучше, чем V*E*logV, особенно, если бы бин. поиск удалось прикрутить. Хотя мб на таком графе (где все единичные рёбра, кроме истока) и тот алгоритм быстрее отработает

[Wataru]

floppa322, Да, в таком графе никак не дополнить поток чем-то больше 1 за один раз. Поэтому прикручивать бинпоиск к ФФ смысла нет.