Здравствуйте, Rumata, Вы писали:

R>Не может ли кто-нибудь подсказать, в какую сторону мне почитать, если я хочу проводить такое разбиение максимально быстро, т.е. для меня не так уж принципиально получить идеальное разбиение.

а что если решить в терминах потоков? максимальный поток минимальной стоимости.
сходу не скажу, но похоже можно в ее терминах описать и решить соответствующими методами.