У нас есть сеть. С истоком и стоком. Пропускные способности каждого ребра нам даны. На каждом ходу мы можем выбрать простой путь и пропустить по нему поток. После этого пропускная способность каждого ребра, входящего в данный путь, уменьшается в k раз. Требуется узнать, сколько максимум мы можем протолкнуть потока за m ходов. Если эта задача жутко простая, то хотелось бы еще спросить про такую же задачу, но только, где у каждого ребра разное k. Хотелось бы узнать как можно больше различных решений этих задач.

P.S : Извините за бред, просто в голову пришла данная задача. Извините, если баян или еще что-нибудь. Пожелания по условию приветствуются.

UPD1: Потоком считать вес минимального ребра на этом пути.

UPD2: Требуется максимизировать сумму этих m потоков, что мы пропустили.

UPD3: Учитывая то, что после контеста обычно много народа на кфе, то я апну тему...Да-да, знаю, что нехорошо делаю, но обещаю, что больше так делать не буду ;)..Если хорошего решения у этой задачи не существует, то хотя бы напишите, что это так.