Итак, у меня наконец-то есть время подвести итог.Решение, которое я использовал, состоит в том, чтобы взять исходный график и преобразовать его в следующих шагах.
(Веса в следующем порядке: нижняя граница, поток тока, верхняя граница.)
1.Соедините t с s по ребру (0, 0, бесконечность).
2.К каждому узлу исходного графа добавьте значение баланса, равное: (сумма нижней границы входящих ребер - сумма нижней границы исходящих ребер).
3.Установите верхнюю границу каждого ребра в (верхняя граница - нижняя граница).Установите нижнюю границу и ток каждого ребра равным 0.
4.Теперь создайте новые s (s ') и новые t (t'), которые будут нашими новыми началом и концом (НЕ УДАЛЯЙТЕ s и t уже в графе, они просто стали нормальными узлами).
5.Создайте ребро от s 'до каждой вершины с положительным балансом с границами (0, 0, vertex.balance).
6.Создайте ребро из каждой вершины с отрицательным балансом до t 'с помощью (0, 0, abs (vertex.balance)).
7.Запустите Ford-Fulkerson (или другой алгоритм максимального потока по вашему выбору) на новом графике.
8.Для каждого ребра начального графа суммируйте значение ребра с начальной старой нижней границей перед преобразованием, и у вас есть начальные потоки для каждого ребра начального графа.
Эта проблема на самом деле немного сложнее, чемчтобы максимизировать поток, когда возможный поток обеспечен.