Изменения
Нет описания правки
Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.
Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> — величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> — общее количество испорченных клеток.
=== Оценка времени работы ===
Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <tex>O(E|f|)</tex>, где <tex>|f|</tex> - величина найденного максимального потока. Заметим, что <tex>|f| <= K / 2</tex>, где <tex>K</tex> - общее количество испорченных клеток. Также заметим, что <tex>E <= K \times 4</tex>, т.к. <tex>K</tex> рёбер исходят из истока и входят в сток и максимум <tex>4</tex> ребра могут исходить из вершины в левой доле в правую. Из всего этого следует, что итоговое время работы будет <tex>O(K^2)</tex>
==Пример №3. Коллекционер монет.==
{{Задача
== См.также ==
* [[Схема алгоритма Диница]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алгоритм масштабирования потока]]
