Изменения

Сначала проверим, что <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>1</tex> в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более <tex>k-1</tex> монеты, которых у него <tex>k</tex> (<tex>k > 1)</tex>). Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности <tex>1</tex> из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью <tex>k_i - 1</tex> в вершину <tex>i</tex>, соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.