Цикл отрицательной стоимости в двудольном графе

[Symbolist]

Подскажите, как создать оптимальный алгоритм поиска цикла отрицательной стоимости, учитывая, что исходный граф является двудольный. Пробовал алгоритм Флойда (цикл отриц. стоимости сущ., если в ходе работы алгоритма на диагонали матрицы смежности появилось отрицательное значение) и Беллмана-Форда (цикл отриц. сотоимости сущ., если после выполнения |V| - 1 итерации алгоритма выполняется еще одна). Желательна трудоемкость не хуже O(|V|*|E|) на матрице, где элемент (i, j) - вес дуги из i-ой вершины одной доли в j-ую вершину другой, причем если (i, j) >= 0, то дуга соединяет i-ю вершины первой доли с j-ой вершиной второй доли, (i, j) < 0, то дуга соединяет i-ю вершины второй доли с j-ой вершиной первой доли (вес все равно остается отрицательным).
Все началось с задачи о нахождении минимального/максимального взвешенного паросочетания.