Определение минимального потока в графе с наименьшей стоимостью с учетом условия

Question

Я недавно готовился к конкурсу acm-icpc.Здесь я хочу узнать, как найти минимальный поток с наименьшей стоимостью при условии, что у каждого ребра в графе есть емкость C, стоимость V и нижний поток L (L ≤ C).

Answer 1

и удачи в соревнованиях!

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

Я взял урок, который вел Роберт Тарьян. Оказалось, что он помог разработать метод получения минимальных потоков, называемый «отмена цикла». Вот отличная лекция Кевина Уэйна, старшего лектора в Принстоне (вместе с Тарьяном): http://www.cs.princeton.edu/~wayne/papers/ratio_talk.pdf

Отмена минимальной средней цепи , в частности, поможет вам найти минимальные потоки.

Если вы просматриваете эти две статьи и все еще хотели бы обсудить их, пожалуйста, дайте мне знать.

Answer 2

Я думаю, что ваш вопрос не очень точный.

Являются ли C, L и V одной константой, которая применяется ко всем ребрам, или они являются векторными? Поскольку вы предоставляете минимальный поток для ребер, я предполагаю, что ваш граф имеет направленные ребра такой, что поток возможен только в одном направлении. Другой момент, требующий пояснения, заключается в том, что стоимость V равна единице потока? Я предполагаю, что да, так как в противном случае стоимость любого потока будет E.V для L> 0.

Таким образом, с этими допущениями вы хотите минимальное обращение цены проблема.

Answer 3

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

Во-вторых, нижняя граница потоков означает, что нетрудно найти «законный поток», который представляет собой поток, в котором соблюдается сохранение массы, т. Е. Сумма входящих потоков равна сумме исходящих потоков. для всех узлов, кроме источника и приемника. (Обычно проблемы потока имеют L = 0, что означает, что нулевой поток является законным.) На самом деле, есть варианты L и C, для которых нет никакого законного потока.

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

Как только вы найдете допустимый поток, тогда алгоритмы Ford-Fulkerson или pre-push-push могут оптимизировать ваш поток (измените его, чтобы снизить общую стоимость).