Тема: Задача про MinCost
http://acm.timus.ru/problem.aspx?space= … ;locale=ru
Есть задача про фараонов. Объясните, плз, как в этой задаче составить граф и вообще применить MinCost?
1 2010-10-02 23:04:29 Отредактировано LebedevNicolay (2010-10-02 23:06:24)
Re: Задача про MinCost
Предположим что размеры прямоугольника четные. Тогда симметричный прямоугольник однозначно характеризуется верхней левой четвертью. Если же есть нечетные стороны, то стоит включить еще половину центральной строки(столбца).
Для каждой такой симметричной четверки (либо двойки или единицы, в случае нечетных длин сторон) определим стоимость перетаскивания в нее каждой статуи (она равна 0 или 1).
Теперь мы можем построить двудольный граф, где в левой половине находятся статуи, а в правой - симметричные группы ячеек. Все ребра из левой доли в правую имеют пропускную способность 1, а так же вес 1 или 0 (определен выше). От истока добавим ребра пр. спос. 1 ко всем статуям, а от всех симметричных групп проведем ребра к стоку пр. спос. бесконечность. Тогда минимальная стоимость максимального потока и будет ответом. Либо же это можно делать венгерским алгоритмом - кому как больше нравится.
Re: Задача про MinCost
По-моему ты что-то недообъяснил...
Как тогда определяется то что в одной четверке будет один тип статуй?
4 2010-10-04 16:31:59 Отредактировано KADR (2010-10-04 16:32:36)
Re: Задача про MinCost
Я даже забыл что стороны четные 
Ну так в каждой четверке должны обязательно стоять статуи одного типа. Значит, количество статуй каждого типа делится на 4. Поделим эти все количества на 4. Ребра идут из четверок статуй одного типа в симметричные четверки.