Время работы алгоритмов поиска потока максимальной стоимости

[Grom1]

Добрый день.

При работе над одной задачей в качестве одного из вариантов рассматриваю сведение ее к задаче о поиске потока минимальной стоимости в большой сети. Вершин порядка $10^3-10^4$, дуг порядка $10^6-10^7$, пропускные способности и стоимости в основном (может быть, за исключением нескольких дуг) - в пределах 10, целочисленные. Дуг ненулевой стоимости - порядка $10^4-10^5$.

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

Если это более-менее реально, то интересует также такой вопрос: по-хорошему, мне нужен не всякий максимальный поток, а только поток, не содержащий частично насыщенных ребер (т.е. каждая дуга в сети либо насыщено, либо поток через нее равен нулю). Поток минимальной стоимости, соответственно, ищется только среди таких.
По реализации этого требования есть идея в алгоритме Форда-Фолкерсона при нахождении f-дополняющей цепи с ненасыщенной дугой (u, v) искать f-дополняющие цепи, начинающиеся в u и заканчивающиеся в источнике, стоке или v, затем то же самое для v. Затем пускать поток минимальной из этих двух величин с тем, чтобы увеличить поток через (u, v). Если дуга все еще ненасыщена - повторить. Если в процессе получаем еще ненасыщенные дуги - выполняем то же для них.

Соответственно, второй вопрос - по осуществимости такого требования. Насколько корректен мой алгоритм? Есть ли варианты лучше? Сколько будет работать итоговый алгоритм с учетом обработки этого требования?