10
правок
Изменения
Нет описания правки
}}
===Решение===
[[Файл:Coints_task.gif|300px|thumb|right|Жёлтые вершины - монеты разных типов, синие - коллекционеры. Красное ребро означает, что коллекционеру нужна монета этого типа, зелёное - что у него больше одной монеты данного типа]]
Построим сеть следующего вида: создадим для каждого типа монет по одной вершине, эти вершины будут соответствовать вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности <tex>1</tex> в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более <tex>k-1</tex> монеты, которых у него <tex>k (k > 1)</tex>. Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности <tex>1</tex> из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью <tex>k_i - 1</tex> в вершину <tex>i</tex>, соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.
== См.также ==
* [[Схема алгоритма Диница]]
