Я дам короткую формальную схему редукции нескольких часто встречающихся формулировок «назначения задач сотрудникам с ограничениями времени», докажу корректность редукции $когдаонакорректна$ и укажу сложность и практические ограничения.

1) Модель$ы$ и предпосылки

Пусть есть n задач J = {j1..jn} и m сотрудников I = {i1..im}.Для каждой задачи j задано требование по времени p_j > 0 $вчасахиливусловныхединицах$ и множество сотрудников S$j$ ⊆ I, которые могут выполнить задачу $понавыкам,повремениит.п.$. Каждая задача должна быть назначена ровно одному сотруднику $есливмоделидопускаетсядробноераспределение,см.ниже$.Для каждого сотрудника i задан общий доступный «временной ресурс» T_i ≥ 0 $количествочасов,котороеонможетпотратить$.Два случая, для которых редукция к максимальному потоку даёт полиномиальное решение:
A. задачи одинаковой «весовой» длины $напримервсеp_j=1$ или задачи дискретны и считаются единицами; каждый сотрудник i может выполнять не более k_i задач $k_i—целое$, где k_i = ⌊T_i / p_unit⌋;
B. допускается дробное $преэмптивное$ распределение задач: p_j можно разделить между несколькими сотрудниками $тогдазадача—поставкаобъёмаp_j,которуюможнораздать$.Важное замечание: если задачи indivisible и p_j различны, и каждая задача должна быть назначена полностью одному сотруднику $бездробления$, то общая проблема является NP‑трудной $умножение/упаковка:bin‑packing/partitionредуцируется$, и полиномиальной редукции к стандартному max‑flow без экспоненциального/псевдополиномиального роста графа в общем случае не существует $еслитолькодополнительныеструктуры/оценкинеприменимы$.

2) Редукция $случайA:единичные/одинаковыезадачи,целочисленноеназначение$ Построим сеть G = $V,E$ с истоком s и стоком t:

Вершины:
s $исток$, t $сток$одна вершина v_j для каждой задачи j $nвершин$одна вершина u_i для каждого сотрудника i $mвершин$Рёбра и пропускные способности $cap$:
(s -> v_j) с cap = 1 для всех задач j $каждаязадача—единичная«единица»,которуюнужнодоставить$(v_j -> u_i) с cap = 1 тогда и только тогда, когда i ∈ S$j$ $т.е.сотрудникiможетвыполнитьзадачуj$(u_i -> t) с cap = k_i, где k_i — максимальное число задач, которое может выполнить i $целое,напримерk_i=\lfloor T_i/p_{u}nit\rfloor$ Запрос: существует ли поток величины n $всезадачиназначены$? Максимизируем поток от s до t.

Корректность $слово—формальное$:

Если в сети существует поток f с величиной |f| = n, то для каждой задачи вершина v_j получает ровно 1 единицу потока от s (т.к. cap(s->v_j)=1), и этот поток должен уйти по какому‑то ребру (v_j->u_i) (поток не может идти s->v_j->t напрямую). Значит каждой задаче соответствует ровно один сотрудник i с f(v_j->u_i) = 1. Для каждого i суммарный поток из u_i в t не превосходит cap(u_i->t) = k_i, значит i не получает более k_i задач. Таким образом поток даёт корректное распределение задач.Обратно, любое корректное распределение задач $каждаязадачаназначенаровноодномусотруднику,ниодинсотрудникнепревышаетk_iзадач$ даёт поток величины n: поставляем 1 по (s->v_j), 1 по соответствующему (v_j->u_i), и суммарно в (u_i->t) = число назначенных задач ≤ k_i. Следовательно максимум потока = максимум числа назначенных задач; «все задачи назначим» ↔ «максимальный поток = n».Интегральность: все capacities целые $0/1иk_iцелые$ ⇒ по теореме интегральности сетевого потока существует целочисленный максимум, т.е. все значения потоков будут целыми, и в частности ребра v_j->u_i будут 0/1, что даёт явное целочисленное назначение.

3) Редукция $случайB:дробное/преэмптивноераспределениезадач$ Построим сеть:

Вершины: s, t, для каждой задачи j — вершина v_j, для каждого сотрудника i — вершина u_i.Рёбра:
(s -> v_j) с cap = p_j $объёмвременизадачи$(v_j -> u_i) с cap = p_j если i ∈ S$j$ $или\infty /p_jдостаточно$ — допускаем дробление потока с v_j к любым допустимым сотрудникам(u_i -> t) с cap = T_i $общийдоступныйресурссотрудника$Тогда существует поток общей величины sum_j p_j $вся«нагрузка»распределена$ тогда и только тогда, когда задачи можно распределить $вдробномсмысле$ так, чтобы суммарное время у каждого i ≤ T_i. Аналогично доказательство двунаправленное: поток → распределение долей p_j, распределение → поток. Здесь не требуется целочисленности — решается обычным max‑flow.

4) Сложность $постройка+решение$

Размер графа: V = n + m + 2; E = n (s->tasks) + |E_bip| (ребра task->employee) + m (employees->t), где |E_bip| = sum_j |S$j$| — число допустимых пар $j,i$.Построение графа: O$V+E$ — пройти по спискам задач и допустимых сотрудников.Решение max‑flow:
Если использован алгоритм Dinic: типичная практическая оценка O$Esqrt(V)$ $влитературедаётсянескольковариантовоценок;дляunit‑capacityграфовчастоO(min(V^{2/3},sqrt(E))<em>E)$. Для аккуратности можно указать: O$E</em>sqrt(V)$ будет разумной оценкой для больших сетей.Для Push‑Relabel с оптимизациями в практических реализациях часто работает быстрее; теоретическая оценка O$V^{2}sqrt(E)$ — хуже в видеуле, но практические библиотеки $HiPR/Goldberg$ очень эффективны.Итак общая асимптотика: O$(n+m+|E_{b}ip|)\ast sqrt(n+m)$ в случае Dinic $приблизительно$.Память: O$V+E$ для представления графа.

5) Ограничения практического применения $когдаредукциянепригоднаилитяжёлая$

Плотные графы: |E_bip| может быть O$n<em>m$. Если n и m порядка десятков тысяч, nm негодится — память и время взорвутся. Практически максимум поток на графе с миллионами рёбер ещё решается, но с сотнями миллионов рёбер — уже проблематично.NP‑трудность общего случая: если задачи indivisible и p_j разные, задача «распределить задачи так, чтобы для каждого i суммарное время ≤ T_i» $аналогмногоконтейнернойупаковки/partition$ в общем случае NP‑трудна. Редукция к max‑flow с полиномиальным ростом графа не даёт решения полного случая. Возможные обходы:
если p_j — маленькие целые числа, можно делать псевдополиномиальную редукцию: разбить каждый сотрудник i на T_i «слотов» $илислотыпоединицевремени$ — даст граф с O$sum{T}_i$ вершин; это может быть применимо, но рост по времени $ипамяти$ большой — псевдополиномиальный.использовать приближённые/эвристические алгоритмы, ILP/CP‑решатели, жадные эвристики или метаэвристики для больших инстанций.Дробление задач: часто в реальности задачи indivisible; если дробление недопустимо, поток решит только специальные случаи $единичныезадачиит.п.$. Если дробление допустимо $параллельизация/передачакусочковработы$ — max‑flow подходит.Временные окна/слоты: если у задач есть временные окна $определённыеинтервалывкалендаре$, то приходится расширять модель по 시간ным слотам, что увеличивает размер графа $вертикальнаядекомпозицияповременнымшагам$ — опять рост графа пропорционален сумме слотов.

6) Практические рекомендации

Для случаев «каждая задача равна одной единице работы» используйте простую редукцию $п.2$ и Dinic / Push‑Relabel — надёжно и быстро для умеренно больших графов $домиллионоврёберприхорошейреализацииипамяти$.Для дробного распределения используйте редукцию п.3 и решатель потока с вещественными или целыми капацитетами.Для вариаций с целью минимизировать суммарные затраты/стоимость назначений используйте Min‑Cost Max‑Flow (аналогичная редукция + стоимости на рёбрах task->employee).Если граф слишком плотный — сначала сократите: отсеките невозможные пары, предфильтруйте сотрудников по навыкам/пространству, используйте жадные алгоритмы или ILP с отсеиванием.При NP‑трудном общем случае применяйте аппроксимации/эвристики или псевдополиномиальную дискретизацию если p_j небольшие.

7) Короткая теорема корректности $формально,дляслучаяA$ Теорема. Построенная сеть имеет максимальный поток равный n ⇔ существует назначение всех n задач сотрудникам с ограничениями k_i.
Доказательство. $Кратко$ См. доводы в п.2: поток→назначение $каждойзадачесоответствуетровноодинсотрудник$, назначение→построение потока $направитьпосоответствующимрёбрам$, интегральность гарантирована целыми capacities. □

Если нужно, могу:

привести псевдокод для реализации $построениеграфа+вызовбиблиотекиmax‑flow$;показать пример численного преобразования для конкретного входа;разобрать случай «задачи с временными окнами» и как их дискретизировать в слот‑граф $соценкойростаразмера$.