Изменения

|definition = Дан паркет размером NxM<tex>N \times M</tex>, некоторые клетки которого испорчены, их необходимо закрыть новыми плитками. Плитки бывают размером 2х1 <tex>2 \times 1</tex> ценой А<tex>A</tex>, и 1х1 <tex>1 \times 1</tex> ценой <tex>B</tex>. Плитки можно поворачивать, но нельзя разрезать. Какую минимальную сумму нужно потратить, что бы заложить испорченные плитки паркета. Новые плитки не должны перекрывать никакие другие плитки.

Сначала проверим, что <tex>2*B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками 1х1 <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой А.Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки 2х1 <tex>2 \times 1</tex> будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в <tex>1 </tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f </tex> — величина найденного максимального потока между истоком и стоком, это и будет количество плиток 2х1<tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f*A+(K-f)*B</tex>, где <tex>K </tex> — общее количество испорченных клеток.