Обсуждение:Поток минимальной стоимости

Материал из Викиконспекты
Перейти к: навигация, поиск

Здесь [math]f[/math] -- поток, [math]c[/math] -- пропускная способность, а цена-то как обозначается? Мне кажется, в статье под [math]c[/math] в некоторых местах подразумевается стоимость, а в некоторых -- пропускная способность.

  • Шаг 4. При помощи алгоритма Форда-Беллмана найдем отрицательные циклы в остаточной сети (но разве можно найти все циклы сразу?). Если нет — перейдем к шагу 7.
  • Шаг 6. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Перейдем к шагу 5 (но ведь остаточная сеть изменилась и могли появиться новые циклы, которые надо ещё найти).

(асимптотика скорее всего неверная, т.к. не учитывает красные замечания выше)