Как довести задачу на min cost flow?

Question

[floppa322]

Самолет последовательно посещает города от 1 до n. Для каждой пары (i, j) известно, что pi,j пассажиров хотят сесть на самолет в городе i и сойти в городе j. Каждый из этих pi,j пассажиров готов заплатить fi,j денег за поездку. Найдите максимальную прибыль при условии, что самолет может одновременно вместить не более k человек.

Если поток использовать как ограничение на вместимость самолёта, а обратив cost'ы на (-1)*pij*fij и находя кратчайшие (длиннейшие) пути (это можно сделать, потому что получившийся граф - dag) найти min cost, то вроде всё ок, за исключением двух проблем: пассажиры pij могут выйти не на своей станции (рёбра vij->t проблемные) и cost некратный fij

Граф для пар (1,4) и (2, 3) на 5-ти вершинах

Comments

[Wataru]

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

Вы уверены, что задачу можно свести к потокам? Она у вас в теме на потоки дана? Или вы просто подумали, что тут можно потоки применить? Какие ограничения в задаче (насколько большие числа n, k)?

[floppa322]

Wataru, ага, 11 страница

https://neerc.ifmo.ru/teaching/algo/year2022/algo....

[Wataru]

floppa322, Мне здается, что автор задания не заметил эту проблему. Если можете, спросите у преподавателя, а не подразумевается ли вот такое решение в качестве эталонного:
Граф из n вершин + s и t. Ребро из i в i+1 пропускной способностью k, ценой 0. Ребра из s в i пропускными способностсями pij ценами -fij. ребра из i в t пропускными способносями pji ценой 0.
Подразумевается, что любое назначение каких пассажиров берем соответсвует потоку из s ->i ->i+1... -> j -> t. Ограничения на ребрах i->i+1 задают вместимость самолета.

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

[floppa322]

Wataru, на самом деле после задач вроде этой (решение) уже не удивлюсь ни одной упоротой конфигурацией графа, в том смысле что в потоках и разрезах бывают совсем слишком неочевидные структуры решения

[Wataru]

floppa322, Действительно, упорото. Но в этой задаче используется тот факт, что числа небольшие. Поэтому часть вершины соответствуют всем возможным значениям силы каждого волшебника. Кроме того там на каждая переменная "переворачиваем ли конкретную пару" участвует ровно в двух неравенствах. Вот это число 2 и позволяет как-то не ребра это натягивать.

Что-то подобное в задаче про самолет не придумать, тут или мы или берем человека или не берем. И это в контексте потока отлично ложится именно на велечину потока или ребро в разрезе. А дальше опять вылезают сложные условия - каждая переменная втречается в куче неравенств по всем промежуточным перелетам.

[floppa322]

Wataru, у меня осталось только одно направление, в какую сторону можно думать: если представить перелёты как отрезки, то если какие-то 2 пересекаются, то в оба суммарно больше k не войдёт, поэтому если сделать общую вершину вметимостью k у них, то можно ограничить, но тем не мене выглядит бесперспетивно, потому что могут быть и пары и по 3 и по 4 и т.д.. В общем идея была сделать какой-нибудь граф отрезков ну и сверху потоки прикрутить

[Wataru]

floppa322, Этот подход выглядит бесперспективным. Скорее всего составитель задачи ошибся.