Потоки с нижними границами: «не меньше двух врачей на смену»

Если ты умеешь сводить поток с нижними границами к максимальному потоку через избытки вершин и знаешь критерий допустимости, листай до «Теперь сам».

Как думаешь, что делать с «не меньше»

Восемь врачей, четыре отделения. Каждый врач берёт одну-две смены и умеет работать в двух отделениях. Каждому отделению нужно от двух до четырёх смен. Как сеть: исток → врач (1..2), врач → отделение (0..1), отделение → сток (2..4).

Прежде чем читать дальше, ответь себе: алгоритм максимального потока охотно оставит ребро пустым, если так выгоднее. Как заставить его пустить по ребру хотя бы два? И как вообще узнать, что расписания нет - если в одно отделение умеет ходить только один врач?

На что это похоже

Обязательные платежи в бюджете. Прежде чем распределять свободные деньги, из каждой статьи вычитают минимум: аренда, зарплата, налоги - их заплатят в любом случае. После этого у кого-то образовалась «дыра» (обязательный платёж больше, чем приходит), а у кого-то «излишек». Вопрос бюджета превращается в вопрос: можно ли перекачать излишки в дыры по имеющимся каналам? Нижние границы - обязательные платежи, а перекачка - обычный поток.

Механизм: аванс, избытки, проверка насыщения

ребро u → v с границами [l, c]:
    пустили l авансом:  ёмкость остатка c − l
    избыток(v) += l      (в v пришло l)
    избыток(u) −= l      (из u ушло l)

новая сеть:
    рёбра с ёмкостями c − l
    t → s с бесконечной ёмкостью    (поток в задаче идёт по кругу)
    S → x ёмкостью избыток(x),  если он > 0
    x → T ёмкостью −избыток(x), если он < 0

максимальный поток S → T:
    насыщает все рёбра из S  →  допустимый поток есть:
                                f(e) = найденный(e) + l(e)
    не насыщает              →  нижние границы выполнить нельзя

Почему так. Аванс нарушил сохранение: в v пришло лишнее, из u ушло лишнее. Чтобы аванс стал настоящим потоком, лишнее надо отвести из v и подвести к u по оставшимся ёмкостям - ровно это и делает поток из S (подключённого к избыткам) в T (подключённый к недостачам). Ребро t → s разрешает потоку исходной задачи идти от стока обратно к истоку: так исходная задача становится кругом, в котором сохранение выполняется везде, включая s и t.

Если нужен не просто допустимый, а МАКСИМАЛЬНЫЙ поток с нижними границами, после проверки убирают S, T и ребро t → s и дополняют найденный поток обычным алгоритмом от s к t.

Правило

Нижнюю границу пускают авансом: остаётся ёмкость c − l, у конца ребра избыток +l, у начала −l. Избытки подключают к новому истоку S, недостачи - к новому стоку T, добавляют t → s без ограничения и ищут максимальный поток S → T. Поток насытил все рёбра из S - допустимое решение есть, и f = найденный + l; не насытил - задача невыполнима, и минимальный разрез показывает почему.

Разбор: четыре ребра

s→a [2,3]   a→t [0,1]   a→b [0,5]   b→t [1,4]

аванс:  ёмкости  s→a 1, a→t 1, a→b 5, b→t 3
        избытки  a: +2,  s: −2,  t: +1,  b: −1
новая сеть: S→a 2, S→t 1, s→T 2, b→T 1, t→s ∞
нужно насытить S: 2 + 1 = 3

поток S → T:
    S→a→b→T       1
    S→a→t→s→T     1      (a→t насыщено)
    S→t→s→T       1
насыщено 3 из 3 → допустимо

настоящий поток = найденный + нижние границы:
    s→a 0+2 = 2,  a→t 1+0 = 1,  a→b 1+0 = 1,  b→t 0+1 = 1
проверка: в a пришло 2, ушло 1 + 1;  в b пришло 1, ушло 1

Нижняя граница s→a ≥ 2 выполнена авансом, а остаток распределился так, чтобы и b→t ≥ 1 было выполнено. Величина потока - 2.

Разбор: врачи и отделения

Программа строит сеть «врач - отделение» со случайными навыками, ищет допустимое расписание и проверяет сохранение и все границы. Потом один врач осваивает недостающее отделение - и задача пересчитывается.

import random
from collections import deque


def maks_potok(cap, s, t):            # Эдмондс-Карп на словаре рёбер
    ost, sos = dict(cap), {}
    for (u, v) in cap:
        ost.setdefault((v, u), 0)
    for (u, v) in ost:
        sos.setdefault(u, []).append(v)
    znach = 0
    while True:
        otec, och = {s: None}, deque([s])
        while och and t not in otec:
            u = och.popleft()
            for v in sos.get(u, []):
                if ost[u, v] > 0 and v not in otec:
                    otec[v] = u
                    och.append(v)
        if t not in otec:
            return znach, {e: cap[e] - ost[e] for e in cap}
        put, v = [], t
        while otec[v] is not None:
            put.append((otec[v], v))
            v = otec[v]
        d = min(ost[e] for e in put)
        for u, v in put:
            ost[u, v] -= d
            ost[v, u] += d
        znach += d


def s_nizhnimi(rebra, s, t):          # rebra: (u, v) -> (низ, верх)
    cap, izb = {}, {}
    for (u, v), (lo, hi) in rebra.items():
        cap[u, v] = hi - lo           # сверх нижней границы
        izb[v] = izb.get(v, 0) + lo   # lo уже «пришло» в v
        izb[u] = izb.get(u, 0) - lo   # и «ушло» из u
    cap[t, s] = 10 ** 9               # круговорот t → s
    nuzhno = 0
    for x, e in izb.items():
        if e > 0:
            cap["S", x] = e
            nuzhno += e
        elif e < 0:
            cap[x, "T"] = -e
    znach, f = maks_potok(cap, "S", "T")
    if znach < nuzhno:
        return None                   # нижние границы не выполнить
    return {e: f[e] + rebra[e][0] for e in rebra}


rng = random.Random(18)
vrachi = [f"в{i}" for i in range(8)]
otdel = [f"о{j}" for j in range(4)]
rebra = {}
for v in vrachi:                      # каждый врач: 1..2 смены
    rebra["s", v] = (1, 2)
    for o in rng.sample(otdel, 2):
        rebra[v, o] = (0, 1)          # где умеет работать
for o in otdel:                       # отделению: от 2 до 4 смен
    rebra[o, "t"] = (2, 4)
print("умеют работать:",
      {o: sum(1 for e in rebra if e[1] == o) for o in otdel})


def raspisanie():
    f = s_nizhnimi(rebra, "s", "t")
    if f is None:
        return "нет"
    for x in vrachi + otdel:          # проверка сохранения и границ
        vh = sum(f[e] for e in rebra if e[1] == x)
        assert vh == sum(f[e] for e in rebra if e[0] == x)
    assert all(lo <= f[e] <= hi for e, (lo, hi) in rebra.items())
    return [f[o, "t"] for o in otdel]


print("расписание:", raspisanie())
v = next(v for v in vrachi if (v, "о2") not in rebra)
rebra[v, "о2"] = (0, 1)               # ещё один врач освоил о2
print(v, "освоил о2, расписание:", raspisanie())

умеют работать: {'о0': 3, 'о1': 6, 'о2': 1, 'о3': 6}
расписание: нет
в0 освоил о2, расписание: [2, 3, 2, 2]

Первое расписание невозможно, и причина видна из первой строки: в отделение о2 умеет ходить один врач, а нужно две смены, причём одна смена врача в одном отделении - не больше одной. Алгоритм ничего не знает про «умеют работать» - он просто не смог насытить ребро из S, и минимальный разрез прошёл бы ровно через это отделение. Стоило врачу в0 освоить о2 - расписание нашлось: смены по отделениям 2, 3, 2, 2, все нижние границы выполнены.

Что ломается без этого

Первая ошибка - забыть ребро t → s: тогда у s и t нет сохранения, их избытки некуда девать, и допустимые задачи объявляются невыполнимыми. Вторая - перепутать знаки избытков: у конца ребра избыток растёт, у начала - падает; перепутав, получишь «решение», в котором нижние границы нарушены. Третья - вернуть найденный поток без прибавления нижних границ: в ответе окажутся нули там, где требовалось не меньше двух. Четвёртая - пытаться выполнить «не меньше» штрафами в стоимости: штраф делает нарушение дорогим, но не запрещает, и при неудачных числах оптимум его выберет.

Зачем это в работе

Расписания с минимальным составом (смены, дежурства, экзамены с наблюдателями), планы перевозок с обязательными объёмами по контрактам, распределение нагрузки с гарантированным минимумом на сервер, потоки в сетях с обязательствами. Отдельная польза - ответ «НЕВОЗМОЖНО» с причиной: минимальный разрез показывает конкретное узкое место (одно отделение, один врач), и его можно предъявить заказчику, а не спорить о том, что «алгоритм не справился».

Теперь сам

Ребро s→a [3,5], ребро a→t [0,2]. Какие избытки получатся? Есть ли допустимый поток?