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