Изменения

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

Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <tex>O(E|f|)</tex>, где <tex>|f|</tex> - – величина найденного максимального потока. Заметим, что <tex>|f| <= \leqslant \dfrac K / 2</tex>, где <tex>K</tex> - – общее количество число испорченных клеток. Также заметим, что <tex>E <= \leqslant K \times 4</tex>, т.к. <tex>K</tex> рёбер исходят из истока и входят в сток и максимум <tex>4</tex> ребра могут исходить из вершины в левой доле в правую. Из всего этого следует, что итоговое время работы будет <tex>O(K^2)</tex>

[[Файл:Coints_task.gif|300px400px|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>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>