Нужна простая консультация для решения проблемы графа

Question

Мой коллега предложил мне упражнение с веб-сайта онлайн-судьи, что в основном представляет собой проблему решения графа эвакуации в маленьком городке.

Мне не нужен ответ (и я не хочу этого). Мне просто нужен совет, на котором лучший подход к его решению с тех пор, как он стал новым для подобных проблем.

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

проблема заключается в следующем: http://acm.timus.ru/problem.aspx?space=1&num=1237

в случае его форума Херес Google кэшированные версии этого: http://webcache.googleusercontent.com/search?q=cache:t2EPCzezs7AJ:acm.timus.ru/problem.aspx%3Fspace%3D1%26num%3D1237+vladimir+kotov+evacuation+problem&cd=1&hl=pt-PT&ct=clnk&gl=pt

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

любой отзыв приветствуется, пожалуйста, не чувствуйте, что я прошу ответа, я просто хочу совета в правильном направлении его решения.

благодарит заранее.

Answer 1

точно как Transhipment Problem, который может (по-видимому) быть решен с помощью линейного программирования. (Я говорю, по-видимому, потому что это выглядит как экземпляр Integer Linear programming).

С сайта:

Стандартный сценарий, где возникает проблема перевозки является то, что отправки единиц продукта через сети автомобильных дорог, соединяющих заданное множество городов. Каждый город считается либо «источником» в , что единицы должны быть отправлены из там, или в качестве «раковины» в этих единицах . Каждый источник имеет данного источника питания, каждый из которых имеет заданный , а на каждой магистрали, которая соединяет , пара-источник-источник имеет заданную стоимость на единицу . Это можно представить в виде вид сети, как показано на рисунке Рисунок TP-1 ниже.

Учитывая такую ​​сеть, проблема интереса определить оптимальную транспортной схемы, которая сводит к минимуму общей стоимость поставок, при условии на поставку и ограничения спроса.

Надеюсь, что это поможет.

Answer 2

Это похоже на проблему Min-cost max flow. Двусторонний граф с ~ 200 вершинами должен выполняться легко во времени.

Чтобы создать ограничение вершин (каждый узел может обрабатывать только k людей), вам просто нужно создать второй граф G_1, где вы добавляете дополнительную вершину u_i для каждого v_i, и имея поток v_i для u_i, независимо от вашего ограничения в этом случае k + 1 с стоимостью 0. Поэтому в основном, если в исходном графе G есть ребро (a, b), то в G_1 будет ребро (u_a, v_b) для каждого из эти края. По сути, вы создаете второй слой вершин, который ограничивает поток до k для каждой вершины.