У нас есть сеть. С истоком и стоком. Пропускные способности каждого ребра нам даны. На каждом ходу мы можем выбрать простой путь и пропустить по нему поток. После этого пропускная способность каждого ребра, входящего в данный путь, уменьшается в k раз. Требуется узнать, сколько максимум мы можем протолкнуть потока за m ходов. Если эта задача жутко простая, то хотелось бы еще спросить про такую же задачу, но только, где у каждого ребра разное k. Хотелось бы узнать как можно больше различных решений этих задач.
P.S : Извините за бред, просто в голову пришла данная задача. Извините, если баян или еще что-нибудь. Пожелания по условию приветствуются.
UPD1: Потоком считать вес минимального ребра на этом пути.
UPD2: Требуется максимизировать сумму этих m потоков, что мы пропустили.
UPD3: Учитывая то, что после контеста обычно много народа на кфе, то я апну тему...Да-да, знаю, что нехорошо делаю, но обещаю, что больше так делать не буду ;)..Если хорошего решения у этой задачи не существует, то хотя бы напишите, что это так.
Оно там делится с остатком или как?
Дробно.
А что считать пропущенным потоком тогда?
Вес минимального ребра на этом пути. Требуется максимизировать сумму всех потоков за m ходов, если в этом был вопрос.
Пара вопросов:
1. Можно ли пустить поток меньше чем это значение;
2. Правильно ли я понимаю, что если через ребро прошёл поток размера X, то New = (Old — X) / K, где New и Old -- новая и старая пропускные способности, соответственно.
Вот интересно стало, в чем смысл этого поста?
Я понимаю так: пришла в голову идея задачи, придумал решение, оформил, и вот новая, возможно оригинальная, задача для будущих контестов.
А здесь, попытка придумать совместыми усилиями задачу, которая будет засвечена ещё до появления на свет? Или вот именно эта проблема почему-то спать не даёт?
Именно эта задача не дает спать.
UPD : неужели у Вас никогда не было, что Вас настолько заинтересовал бы какой-нибудь вопрос, что Вы спрашиваете, почему я выложил эту задачу?
Конечно, это совершенно естественно задать здесь вопрос.
Просто заголовок у Вас: "(задача собственного сочинения)".
Если это задача, то вопрос странный. Если же просто попытка совместно продвинуть теорию алгоритмов, то это можно только приветствовать.
Ну, вроде бы, это задача)
Ну, тогда по неписанным правилам CF, надо привести источник, и заголовок должен быть "Help me, please" =)
А то мало ли кому по ночам что в голову придет.
Можно было бы тогда залить эту задачу на мозырскую тестирующую систему :)
Не хочу попусту цепляться.
Просто, по-моему, задача — это идея+авторское решение+перекрестное решение+тесты+легенда.
Заливайте.
Действительно, хватит цепляться к ерунде. Надеюсь, этот комментарий станет последним в этой ветке. Видимо я неправильно выразился, назвав это задачей. Вы не первый человек, который придирается к этому.
сделаем из графа мультиграф, вместо оригинального ребра (a, b, W) (W-пропускная способность) у нас появляется C рёбер (a, b, W) (a, b, W/K), (a, b, W/(K^2)) ... (a, b, W/(K^(C-1))) найдём поток в полученном графе. ответ будет отличаться от реального приближенно на 1/K^C. Вроде-бы дальше этот поток будет улучшаться схожим образом, и при желании предел к которому эта байда сходится можно найти аналитически посчитав какие-то параметры проталкивания, и посчитав сумму геометрической прогрессии.
Вот на таком тесте вроде бы не работает.
Ребра(первое и второе число описывают вершины, связанные ребром, последнее число — пропускную способность) :
S 1 100
S 2 100
2 3 100
1 3 100
3 T 1000
k = 100
S — это исток
T — это сток
Ваш алгоритм найдет ответ 202(при C=2), а правильный ответ 110. Поправьте меня, если я ошибся где-то.
Не разбирал пример, но ты ошибся. Пусть мы протолкнули поток m раз, при этому у нас получилось m путей исток-сток. каждое ребро заюзалось сколько-то раз. В первый раз его пропускная способность была W, второй раз W/k и т.д. в вершину старт входит какое-то кол-во вещества, и из конечной столько же выходит. в каких рёбрах поток какого пути проходит значения не имеет. В этом основная идея.
UPD: Нет вру, был не прав.
Но ведь у нас может быть, что мы будем использовать остаток пути, по которому мы шли уже. Или, когда мы будем проталкивать очередной путь, мы будем не уменьшать ребро на величину потока, а сразу обнулять?
я был не прав.
Все равно спасибо за попытку решения :)