## FL5. Карточная игра :::spoiler Подсказка 1 :::info Воспользуйтесь бинарным поиском по ответу. Теперь карту характеризуют только $c_i$ и $p_i$. ::: :::spoiler Подсказка 2 :::info Не теряя общности, предположим, что есть максимум одна карта с $c_i = 1$ (если их несколько, то мы можем использовать только одну из них). Тогда простое число в сумме могут дать только два числа разной чётности. ::: :::spoiler Подсказка 3 :::info Построим двудольный граф, где в левой доле будут все карты с чётным $c_i$, а в правой - с нечётным. Соеденим ребром все пары вершин, у которых $c_i$ в сумме дают простое число. Тогда мы свели задачу к нахождению в этом графе независимого множества с максимальным суммарным весом вершин (независимое множество - множество вершин такое, что любые две вершины в нём не соединены ребром). ::: :::spoiler Решение :::info Создадим в исходном двудольном графе фиктивные вершины $s$ и $t$. Проведём ребра из $s$ в каждую вершину $i$ левой доли с пропускной способностью $p_i$. Аналогично проведём ребра из всех вершин правой доли в $t$. Тогда искомый максимальный вес независимого множества - это сумма всех $p_i$ минус минимальный $s - t$ разрез в получившемся графе. ::: ## FL6. Коллекционирование монет :::spoiler Подсказка :::info Постройте граф потока таким образом, чтобы каждый путь от истока до стока соответствовал серии обменов монетами, у которых имеются дубликаты, начиная с Васи, отдающего один из своих дубликатов, и заканчивая тем, что он получает новую монету. ::: :::spoiler Решение :::info Для каждого человека кроме Васи создадим в графе потока двудольный подграф, описывающий его монеты. Каждой вершине будет соответствовать тип монет. В левой доле будут типы монет, которых нет у этого человека, а в правой - типы монет, которых у него две и более. Пропускная способность у всех вершин левой доли будет 1, у вершин правой доли - количество монет соответствующего типа минус 1. Попарно соединим вершины левой доли с вершинами правой доли рёбрами бесконечной пропускной способности. Пример для $[1, 1, 1, 2, 2, 5]$ и $m = 5$: <img src="https://i.imgur.com/ynT5hwM.png" width="50%" height="50%"> Поток величины $1$, который течёт из левой доли в правую, означает обмен монеты в левой доле на монету в правой доле. Построим аналогично двудольный подграф для Васи, но не будем соединять рёбрами вершины левой и правой доли. Создадим вершины $s$ и $t$. Проведём рёбра бесконечной пропускной способности из $s$ во все вершины правой доли и из всех вершин левой доли в $t$. Во всём графе для каждого типа монет $x$ соединим попарно вершины правых долей, отвечающих за тип $x$ с вершинами левых долей, отвечающих за него. Ответ - максимальный поток из $s$ в $t$. ::: ## MC2. Мороженое :::spoiler Решение :::info Создадим вершину $t$ и проведём рёбра из $a$ и $b$ в $t$. Назначим всем рёбрам пропускную способность $1$ и стоимость единицы потока, равную длине (у рёбер в $t$ длина $0$). Также назначим всем вершинам кроме $c$ и $t$ пропускную способность $1$. Найдём максимальный поток минимальной стоимости из $c$ в $t$. Если ответ существует, то из $a$ в $b$ через $c$ можно дойти по насыщенным рёбрам, причём этот путь будет минимальным по длине. ::: ## MT3. Домино :::spoiler Решение :::info Построим граф, в котором каждая вершина будет соответствовать клетке поля, и проведём рёбра между всеми парами соседних свободных клеток. Тогда получившийся граф будет двудольным, причём в одной доле будут все клетки с чётным номером диагонали, а в другом - с нечётным (шахматный порядок). Найдём в этом графе максимальное паросочетание. ::: ## MT4. Модели компьютеров :::spoiler Подсказка 1 :::info Если условие $a$ вложено в условие $b$ (т. е. $l_b \le l_a \le r_a \le r_b$) и не противоречит ему, то условие $a$ можно удалить. ::: :::spoiler Подсказка 2 :::info Пусть есть три условия $a$, $b$, $c$, причём $l_a \le l_b \le l_c$. Тогда если $a$ не противоречит $b$ и $b$ не противоречит $c$, то и $a$ не противоречит $c$. ::: :::spoiler Подсказка 3 :::info Постройте граф так, чтобы каждому пути соответствовало множество условий, не противоречащих друг другу. ::: :::spoiler Решение :::info Построим граф на условиях. Из условия $a$ будет ребро в условие $b$ если $l_a < l_b$ и $a$ не противоречит $b$. Очевидно, что такой граф ацикличен. Каждому пути в нём будет соответствовать множество не противоречащих друг другу условий. Тогда ответ на задачу - минимальное покрытие этого графа вершинно-непересекающимися путями. :::