О задаче потоке с ограничениями рассказано http://e-maxx.ru/algo/flow_with_limits, там же написан алгоритм решения задачи. И я всегда(после того, как прочитал) думал, что все хорошо. Давно сдал задачку на sgu 176. Flow Construction. А вот сейчас рассмотрел такой пример, и в нем происходит не то, что должно.
Вначале в общих словах. Пусть в графе все ребра (ориентированные) имеют верхнюю границу потока 1, а нижнюю -- все 0, кроме одного (с нижней границей 1). Тогда если в этом графе есть цикл, проходящий через это самое ребро(но не содержащий истока-стока), то алгоритм скажет, что это ребро можно насытить, хотя насытить его можно не всегда. Действительно из нового истока S' будет идти одно ребро, в конец этого ребра, а в T' тоже одно, но из начала. Тогда будет существовать путь из S' в T' (то есть поток не нулевой, то есть не меньше, чем сумма все нижних границ, которая равна 1, значит ребро можно насытить). Почему существует путь из S' в T': выделенное ребро(с нижней границей = 1), участвует в цикле, то есть из конца этого ребра, можно попасть в начало этого ребра. (S' -> конец ребра -> начало ребра -> T').
Конкретный пример:
Граф задан в формате задачи http://acm.sgu.ru/problem.php?contest=0&problem=176
7 7
1 6 1 0
6 2 1 0
2 3 1 1
3 4 1 0
4 5 1 0
5 2 1 0
6 7 1 0
и моя программа, получившая accepted, выдает:
0
0 0 1 1 1 1 0
Хотя насытить ребро 2-3 нельзя.
Получается, ошибка или в алгоритме, или в моих рассуждениях. Буду рад помощи.
Добавлю, что если бы существовал алгоритм, который бы позволял делать то, что вы хотите (находить такой поток, который не пускает ничего по циклам, а только проталкивает от истока к стоку) с минимальными ограниченями на ребра, то присвоение минимального и максимального веса один каждому ребру в гамильтоновом графе находило бы гамильтонов путь за полиномиальное время.