Или можно еще проще: разбиение на циклы равносильно перестановке, которая для каждой вершины задает следующую в цикле. Перестановка равнозначна максимальному паросочетанию.
Действительно, полное парсочетание становится циклами. Да, если граф не ориентированный, или содержит "тривальные" циклы (длины 2), то они могут войти в покрытие. Если найдется не полное паросочетание, то в графе будут какие-то непересечающиеся циклы и возможно пути. Он может быть даже не весь покрыт при этом.
Граф почти такой же. Раздвоенное ребро. В середину каждого ребра вход из истока пропускной способностью 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 и запустить поток дальше. Это будет как если бы вы запустили поток один раз с максимальной пропускной способностью сразу.
For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the entropy of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern.
Если в качестве диапазоно взять ключи, то у вас будет запрос по ключам.
Вы там говорили, что данные не меняются, так что возможно какой-нибудь сортированный массив с одним бинпоиском может быть даже быстрее любой другой структуры данных.
Просто увидев некоторую симметрию с "домино" индукции, там ведь тоже скипается очевидная часть после базы и шага индукции (что теперь нужно взять базу b0 и подставить в доказынный k-й шаг, применив переход и получив базу b1 и так далее), подумал, что мб здесь так же