Сейчас осознал, что задача о потоке минимальной стоимости для случая когда стоимости ребер могут быть отрицательными — NP. Алгоритмы через путь минимальной стоимости не работают из-за отрицательных циклов, а теорема о том что поток имеет минимальную стоимость т.ит.т.к. нет отрицательных циклов для этого случая вообще не верна, хотя ошибка весьма неочевидна. Почему-то я об этом нигде раньше не встречал упоминаний.