Че-то я почитал решения на 1000 на TopCoder Open Online Round 1 и заметил, что оказывается, многие не умеют писать "не обязательно максимальный поток минимальной стоимости", как в транспортной задаче - то есть когда первичный критерий - минимальной стоимости, а не максимальность потока. Я увидел много решений, где люди перебирали размер потока и запускали несколько mincost maxflow - это же не надо так делать :о

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