Изменения
Нет описания правки
Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <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>2 \times 1</tex> и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.
=== Оценка времени работы ===
