Изменения
→Пример №2. Испорченный паркет.
==Пример №2. Испорченный паркет.==
{{Задача
|definition = Дан паркет размером <tex>N \times M</tex>, некоторые клетки которого испорчены, их необходимо закрыть новыми плитками. Плитки бывают размером <tex>2 \times 1</tex> ценой <tex>A</tex>, и <tex>1 \times 1</tex> ценой <tex>B</tex>. Плитки можно поворачивать, но нельзя разрезать. Какую минимальную сумму нужно потратить, что бы чтобы заложить испорченные плитки паркета. Новые плитки не должны перекрывать никакие другие плитки.
}}
===Решение===
Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <tex>O(E|f|)</tex>, где <tex>|f|</tex> – величина найденного максимального потока. Заметим, что <tex>|f| \leqslant \dfrac K 2</tex>, где <tex>K</tex> – общее число испорченных клеток. Также заметим, что <tex>E \leqslant K \times 4</tex>, т.к. <tex>K</tex> рёбер исходят из истока и входят в сток и максимум <tex>4</tex> ребра могут исходить из вершины в левой доле в правую. Из всего этого следует, что итоговое время работы будет <tex>O(K^2)</tex>
==Пример №3. Коллекционер монет.==
{{Задача
