Почему не слышали, что задача в классе NP? Ответ: это очевидно. Но она ещё и лежит в классе P. Есть семейство алгоритмов, которые выбирают отрицательный цикл и пускают по нему поток, некоторые из которых строго полиномиальны. Легко гуглится по словам min mean-cost cycle cancelling.

Я писал, что мне показалось, что это метод вообще неправильный. Но я уже нашел ошибку в своем контрпримере. Теперь опять ничего не понимаю. То есть, у меня как бы есть доказательство P=NP и я уже 3 часа не могу найти в нем ошибку. Теперь буду искать завтра с утра.

Ура. Таки P!=NP?, по крайней мере пока. Ошибка была в неверном понимании потока. Интуитивно, когда дают задачу о потоке говорят, допустим, о системе трубопроводов по которым с минимальной стоимостью надо перекачать что-то из начального пункта в конечный. При этом неявно предполагается, что это что-то есть только в начальном пункте и изначально нигде его больше нет. Так вот, в такой формулировке задача NP-полна. Когда же речь идет о цикруляции, то предполагается, что эти трубопроводы уже как-то заполнены, даже если граф несвязный. Тогда полиномиально.