Применение сетевых потоков

Question

Итак, я недавно начал изучать сетевые потоки (максимальный поток, минимальные срезы и т. Д.), И общие проблемы сетевого потока всегда связаны с назначением «n» чего-либо для «k» другого объекта. Например, как мне настроить сетевой поток для «n» детей в городе, где есть «k» школ, чтобы детские дома находились в пределах x километров от школы (для простоты, скажем, 1 км)?

Что если бы я добавил дополнительные ограничения, например, сказал бы, что в каждой школе не может быть более 100 учеников? Или 300 учеников? Может ли кто-нибудь помочь мне с тем, как я изначально настрою свой алгоритм для решения подобных проблем (был бы признателен за любые ссылки тоже)? Они имеют тенденцию появляться на прошлых промежуточных экзаменах, поэтому я просто хотел быть готовым

Answer 1

Создание вершин для каждого учащегося и каждой школы. Нарисуйте грань вместимостью 1 от каждого учащегося в каждой школе, которую они могут посещать в соответствии с вашим ограничением расстояния. Создайте исходную вершину с ребрами для каждого ученика с вместимостью 1. Создайте вершину-приемник с ребрами, приходящими из каждой школы, с емкостями, равными максимальной вместимости каждой школы.

Выполнение стандартного алгоритма максимального потока подойдет как можно большему числу учащихся к школам. Конечно, не каждому учащемуся гарантировано ходить в школу, учитывая ограничения.

Это, по сути, модификация стандартного алгоритма согласования двухстороннего максимума. Основное различие заключается в том, что вместимость раковин превышает 1, что позволяет сопоставить нескольких учеников со школой.