10
правок
Изменения
Нет описания правки
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке ]]
==Пример №2. Испорченный паркет.==
{{Задача
|definition = Дан паркет размером NxM, некоторые клетки которого испорчены, их необходимо закрыть новыми плитками. Плитки бывают размером 2х1 ценой А, и 1х1 ценой B. Плитки можно поворачивать, но нельзя разрезать. Какую минимальную сумму нужно потратить, что бы заложить испорченные плитки паркета. Новые плитки не должны перекрывать никакие другие плитки.
}}
===Решение===
Сначала проверим, что 2*B>A. Если это условие не выполнено, то все выгодней замостить только плитками 1х1 и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой А.
Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки 2х1 будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в 1 проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай f — величина найденного максимального потока между истоком и стоком, это и будет количество плиток 2х1. Ответом к задаче будет величина f*A+(K-f)*B, где K — общее количество испорченных клеток.
== См.также ==
== Источники информации ==
* [https://icpc.baylor.edu/regionals/finder/west-siberian-subregional-2016 The 2016 West Siberian Subregional Contest]
* Источник: Харьковская зимняя школа по программированию, 2009, День 3
