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