Изменения

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

{| cellpadding="3" style="margin-left: auto; margin-right: auto;"| [[Файл:Parquet_example_1.png|thumb|400px|Пример паркета]]| [[Файл:Parquet_example_2.png|thumb|400px|Пример раскраски]]|}Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой – на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая – черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в 1 и сток с ребрами из черных клеток весом тоже в 1. Пускай <tex>f</tex> – величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> – общее число испорченных клеток.

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

[[Файл:Coints_task.gif|400px|thumb|right|Жёлтые вершины – монеты разных типов, синие – коллекционеры. Красное ребро означает, что коллекционеру нужна монета этого типа, причём пропускная способнасть этого ребра равна 1, зелёное – что у него больше одной монеты данного типа]]Построим сеть следующего вида: создадим для каждого типа монет по одной вершине, эти вершины будут соответствовать вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности <tex>1</tex> в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более <tex>k-1</tex> монеты, которых у него <tex>k </tex> <tex>(k > 1)</tex>. Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности <tex>1</tex> из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью <tex>k_i - 1</tex> в вершину <tex>i</tex>, соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.===Доказательство корректности===Как уже было сказано, построенная сеть отражает процессы обмена в клубе, пример можно посмотреть на картинке выше. Заметим следующее: * из вершины каждого типа монет может выйти поток, величина которого <tex>\leqslant 1 </tex>* в вершины каждого типа монет может войти поток, величина которого не больше количества монет данного типа* если коллекционеру нужна эта монета и мы решили дать её, то мы дадим максимум одну монету этого типа, т.к. пропускная способность красного ребра <tex>= 1</tex>.* если в данную вершину пришёл поток данной величины, то мы должны отдать из этой вершины поток такой же величины. (Из определения потока)Всё вышесказанное подтверждает то, что построенная сеть корректно отображает процессы обмена монетами между участниками. === Оценка времени работы === Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <tex>O(E|f|)</tex>, где <tex>|f|</tex> – величина найденного максимального потока. Заметим, что <tex>|f| \leqslant M</tex>, где <tex>M</tex> – количество типов монет. Также заметим, что <tex>E = M \times 2 + E^*</tex>, где <tex>E^*</tex> – общее минимальное число монет, которые нужно получить все коллекционерам (кроме вас), чтобы вступить в клуб <tex>+</tex> сумма типов монет, которых больше <tex>1</tex>, по всем коллекционерам. Из всего этого следует, что итоговое время работы будет <tex>O(ME)</tex>