http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&feed=atom&action=historyПримеры сведения к задачам поиска потока - История изменений2024-03-29T15:45:43ZИстория изменений этой страницы в викиMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=85177&oldid=prevMaintenance script: rollbackEdits.php mass rollback2022-09-04T16:26:25Z<p>rollbackEdits.php mass rollback</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 16:26, 4 сентября 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|+</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|-align="center"</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|'''НЕТ ВОЙНЕ'''</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|-style="font-size: 16px;"</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">''Антивоенный комитет России''</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|-style="font-size: 16px;"</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|-style="font-size: 16px;"</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">|}</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Рассмотрим несколько задач, которые решаются путём сведения к задаче о поиске максимального потока в сети.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Рассмотрим несколько задач, которые решаются путём сведения к задаче о поиске максимального потока в сети.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>Maintenance scripthttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=83429&oldid=prev103.251.167.21 в 04:55, 1 сентября 20222022-09-01T04:55:45Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 04:55, 1 сентября 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|+</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|-align="center"</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|'''НЕТ ВОЙНЕ'''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|-style="font-size: 16px;"</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">''Антивоенный комитет России''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|-style="font-size: 16px;"</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|-style="font-size: 16px;"</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">|}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Рассмотрим несколько задач, которые решаются путём сведения к задаче о поиске максимального потока в сети.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Рассмотрим несколько задач, которые решаются путём сведения к задаче о поиске максимального потока в сети.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>103.251.167.21http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=82194&oldid=prev178.66.157.249: /* Пример №3. Коллекционер монет. */2022-01-29T09:24:18Z<p><span dir="auto"><span class="autocomment">Пример №3. Коллекционер монет.</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 09:24, 29 января 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l63" >Строка 63:</td>
<td colspan="2" class="diff-lineno">Строка 63:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Пример №3. Коллекционер монет.==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Пример №3. Коллекционер монет.==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{Задача</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{Задача</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>|definition=Есть <tex>N</tex> коллекционеров и <tex>M</tex> видов монет. Для вступления в клуб, необходимо иметь не меньше одной монеты каждого типа. Вы (у вас номер 1) можете меняться с коллекционерами имеющимися монетами. Любой коллекционер обменяет <del class="diffchange diffchange-inline">монету </del>свою монету <tex>a</tex> на вашу монету <tex>b</tex>, если у него '''больше''' одной монеты типа <tex>a</tex> и нету ни одной монеты типа <tex>b</tex>. Вы, в свою очередь, можете нарушать это правило. Нужно набрать как можно больше типов монет по известной ситуации у всех коллекционеров.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>|definition=Есть <tex>N</tex> коллекционеров и <tex>M</tex> видов монет. Для вступления в клуб, необходимо иметь не меньше одной монеты каждого типа. Вы (у вас номер 1) можете меняться с коллекционерами имеющимися монетами. Любой коллекционер обменяет свою монету <tex>a</tex> на вашу монету <tex>b</tex>, если у него '''больше''' одной монеты типа <tex>a</tex> и нету ни одной монеты типа <tex>b</tex>. Вы, в свою очередь, можете нарушать это правило. Нужно набрать как можно больше типов монет по известной ситуации у всех коллекционеров.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td></tr>
</table>178.66.157.249http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=74475&oldid=prev81.151.111.74: /* Решение */2020-06-14T15:23:54Z<p><span dir="auto"><span class="autocomment">Решение</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 15:23, 14 июня 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l53" >Строка 53:</td>
<td colspan="2" class="diff-lineno">Строка 53:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>|}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>|}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой – на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая – черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в <del class="diffchange diffchange-inline">бесконечность </del>и сток с ребрами из черных клеток весом тоже в <del class="diffchange diffchange-inline">бесконечность</del>. Пускай <tex>f</tex> – величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> – общее число испорченных клеток.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой – на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая – черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в <ins class="diffchange diffchange-inline">1 </ins>и сток с ребрами из черных клеток весом тоже в <ins class="diffchange diffchange-inline">1</ins>. Пускай <tex>f</tex> – величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> – общее число испорченных клеток.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Доказательство корректности===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Доказательство корректности===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Заметим следующее: мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот – это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером <tex>2 \times 1</tex> и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Заметим следующее: мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот – это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером <tex>2 \times 1</tex> и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.</div></td></tr>
</table>81.151.111.74http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=71325&oldid=prev77.234.212.37: /* Пример №2. Испорченный паркет. */2019-05-31T07:44:09Z<p><span dir="auto"><span class="autocomment">Пример №2. Испорченный паркет.</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 07:44, 31 мая 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l45" >Строка 45:</td>
<td colspan="2" class="diff-lineno">Строка 45:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Пример №2. Испорченный паркет.==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Пример №2. Испорченный паркет.==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{Задача</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{Задача</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>|definition = Дан паркет размером <tex>N \times M</tex>, некоторые клетки которого испорчены, их необходимо закрыть новыми плитками. Плитки бывают размером <tex>2 \times 1</tex> ценой <tex>A</tex>, и <tex>1 \times 1</tex> ценой <tex>B</tex>. Плитки можно поворачивать, но нельзя разрезать. Какую минимальную сумму нужно потратить, <del class="diffchange diffchange-inline">что бы </del>заложить испорченные плитки паркета. Новые плитки не должны перекрывать никакие другие плитки.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>|definition = Дан паркет размером <tex>N \times M</tex>, некоторые клетки которого испорчены, их необходимо закрыть новыми плитками. Плитки бывают размером <tex>2 \times 1</tex> ценой <tex>A</tex>, и <tex>1 \times 1</tex> ценой <tex>B</tex>. Плитки можно поворачивать, но нельзя разрезать. Какую минимальную сумму нужно потратить, <ins class="diffchange diffchange-inline">чтобы </ins>заложить испорченные плитки паркета. Новые плитки не должны перекрывать никакие другие плитки.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l59" >Строка 59:</td>
<td colspan="2" class="diff-lineno">Строка 59:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <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></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <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></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Пример №3. Коллекционер монет.==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Пример №3. Коллекционер монет.==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{Задача</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{Задача</div></td></tr>
</table>77.234.212.37http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=59557&oldid=prev176.59.22.229 в 20:00, 10 января 20172017-01-10T20:00:20Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 20:00, 10 января 2017</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l55" >Строка 55:</td>
<td colspan="2" class="diff-lineno">Строка 55:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой – на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая – черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> – величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> – общее число испорченных клеток.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой – на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая – черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> – величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> – общее число испорченных клеток.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Доказательство корректности===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Доказательство корректности===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Заметим следующее: <del class="diffchange diffchange-inline">по сути </del>мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот – это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером <tex>2 \times 1</tex> и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Заметим следующее: мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот – это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером <tex>2 \times 1</tex> и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>176.59.22.229http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=59556&oldid=prev176.59.22.229 в 19:59, 10 января 20172017-01-10T19:59:40Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 19:59, 10 января 2017</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l48" >Строка 48:</td>
<td colspan="2" class="diff-lineno">Строка 48:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Файл:Parquet_example_1.png|Пример паркета]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">{| cellpadding="3" style="margin-left: auto; margin-right: auto;"</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Файл:Parquet_example_2.png|Пример раскраски]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">| </ins>[[Файл:Parquet_example_1.png<ins class="diffchange diffchange-inline">|thumb|400px</ins>|Пример паркета]]</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">| </ins>[[Файл:Parquet_example_2.png<ins class="diffchange diffchange-inline">|thumb|400px</ins>|Пример раскраски]]</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">|}</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой – на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая – черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> – величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> – общее число испорченных клеток.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой – на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая – черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> – величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> – общее число испорченных клеток.</div></td></tr>
</table>176.59.22.229http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=59555&oldid=prev176.59.22.229 в 19:54, 10 января 20172017-01-10T19:54:04Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 19:54, 10 января 2017</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l52" >Строка 52:</td>
<td colspan="2" class="diff-lineno">Строка 52:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой <del class="diffchange diffchange-inline">— </del>на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая <del class="diffchange diffchange-inline">— </del>черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> <del class="diffchange diffchange-inline">— </del>величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> <del class="diffchange diffchange-inline">— </del>общее <del class="diffchange diffchange-inline">количество </del>испорченных клеток.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой <ins class="diffchange diffchange-inline">– </ins>на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая <ins class="diffchange diffchange-inline">– </ins>черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> <ins class="diffchange diffchange-inline">– </ins>величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> <ins class="diffchange diffchange-inline">– </ins>общее <ins class="diffchange diffchange-inline">число </ins>испорченных клеток.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Доказательство корректности===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Доказательство корректности===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Заметим следующее: по сути мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот <del class="diffchange diffchange-inline">- </del>это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером <tex>2 \times 1</tex> и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Заметим следующее: по сути мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот <ins class="diffchange diffchange-inline">– </ins>это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером <tex>2 \times 1</tex> и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <tex>O(E|f|)</tex>, где <tex>|f|</tex> <del class="diffchange diffchange-inline">- </del>величина найденного максимального потока. Заметим, что <tex>|f| <del class="diffchange diffchange-inline"><= </del>K <del class="diffchange diffchange-inline">/ </del>2</tex>, где <tex>K</tex> <del class="diffchange diffchange-inline">- </del>общее <del class="diffchange diffchange-inline">количество </del>испорченных клеток. Также заметим, что <tex>E <del class="diffchange diffchange-inline"><= </del>K \times 4</tex>, т.к. <tex>K</tex> рёбер исходят из истока и входят в сток и максимум <tex>4</tex> ребра могут исходить из вершины в левой доле в правую. Из всего этого следует, что итоговое время работы будет <tex>O(K^2)</tex></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <tex>O(E|f|)</tex>, где <tex>|f|</tex> <ins class="diffchange diffchange-inline">– </ins>величина найденного максимального потока. Заметим, что <tex>|f| <ins class="diffchange diffchange-inline">\leqslant  \dfrac </ins>K 2</tex>, где <tex>K</tex> <ins class="diffchange diffchange-inline">– </ins>общее <ins class="diffchange diffchange-inline">число </ins>испорченных клеток. Также заметим, что <tex>E <ins class="diffchange diffchange-inline">\leqslant </ins>K \times 4</tex>, т.к. <tex>K</tex> рёбер исходят из истока и входят в сток и максимум <tex>4</tex> ребра могут исходить из вершины в левой доле в правую. Из всего этого следует, что итоговое время работы будет <tex>O(K^2)</tex></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Пример №3. Коллекционер монет.==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Пример №3. Коллекционер монет.==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{Задача</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{Задача</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l63" >Строка 63:</td>
<td colspan="2" class="diff-lineno">Строка 63:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Файл:Coints_task.gif|<del class="diffchange diffchange-inline">300px</del>|thumb|right|Жёлтые вершины <del class="diffchange diffchange-inline">- </del>монеты разных типов, синие <del class="diffchange diffchange-inline">- </del>коллекционеры. Красное ребро означает, что коллекционеру нужна монета этого типа, причём пропускная способнасть этого ребра равна 1, зелёное <del class="diffchange diffchange-inline">- </del>что у него больше одной монеты данного типа]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Файл:Coints_task.gif|<ins class="diffchange diffchange-inline">400px</ins>|thumb|right|Жёлтые вершины <ins class="diffchange diffchange-inline">– </ins>монеты разных типов, синие <ins class="diffchange diffchange-inline">– </ins>коллекционеры. Красное ребро означает, что коллекционеру нужна монета этого типа, причём пропускная способнасть этого ребра равна 1, зелёное <ins class="diffchange diffchange-inline">– </ins>что у него больше одной монеты данного типа]]</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Построим сеть следующего вида: создадим для каждого типа монет по одной вершине, эти вершины будут соответствовать вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности <tex>1</tex> в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более <tex>k-1</tex> монеты, которых у него <tex>k (k > 1)</tex>. Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности <tex>1</tex> из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью <tex>k_i - 1</tex> в вершину <tex>i</tex>, соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Построим сеть следующего вида: создадим для каждого типа монет по одной вершине, эти вершины будут соответствовать вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности <tex>1</tex> в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более <tex>k-1</tex> монеты, которых у него <tex>k<ins class="diffchange diffchange-inline"></tex> <tex></ins>(k > 1)</tex>. Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности <tex>1</tex> из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью <tex>k_i - 1</tex> в вершину <tex>i</tex>, соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Доказательство корректности===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Доказательство корректности===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Как уже было сказано, построенная сеть отражает процессы обмена в клубе, пример можно посмотреть на картинке выше. Заметим следующее:  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Как уже было сказано, построенная сеть отражает процессы обмена в клубе, пример можно посмотреть на картинке выше. Заметим следующее:  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* из вершины каждого типа монет может выйти поток, величина которого <tex><del class="diffchange diffchange-inline"><= </del>1 </tex></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* из вершины каждого типа монет может выйти поток, величина которого <tex><ins class="diffchange diffchange-inline">\leqslant </ins>1 </tex></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* в вершины каждого типа монет может войти поток, величина которого не больше количества монет данного типа</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* в вершины каждого типа монет может войти поток, величина которого не больше количества монет данного типа</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* если коллекционеру нужна эта монета и мы решили дать её, то мы дадим максимум одну монету этого типа, т.к. пропускная способность красного ребра <tex>= 1</tex>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* если коллекционеру нужна эта монета и мы решили дать её, то мы дадим максимум одну монету этого типа, т.к. пропускная способность красного ребра <tex>= 1</tex>.</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l74" >Строка 74:</td>
<td colspan="2" class="diff-lineno">Строка 74:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <tex>O(E|f|)</tex>, где <tex>|f|</tex> <del class="diffchange diffchange-inline">- </del>величина найденного максимального потока. Заметим, что <tex>|f| <del class="diffchange diffchange-inline"><= </del>M</tex>, где <tex>M</tex> <del class="diffchange diffchange-inline">- </del>количество типов монет. Также заметим, что <tex>E = M \times 2 + E^*</tex>, где <tex>E^*</tex> <del class="diffchange diffchange-inline">- </del>общее минимальное <del class="diffchange diffchange-inline">количество </del>монет, которые нужно получить все коллекционерам (кроме вас), чтобы вступить в клуб <tex>+</tex> сумма типов монет, которых больше <tex>1</tex>, по всем коллекционерам. Из всего этого следует, что итоговое время работы будет <tex>O(ME)</tex></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы <tex>O(E|f|)</tex>, где <tex>|f|</tex> <ins class="diffchange diffchange-inline">– </ins>величина найденного максимального потока. Заметим, что <tex>|f| <ins class="diffchange diffchange-inline">\leqslant </ins>M</tex>, где <tex>M</tex> <ins class="diffchange diffchange-inline">– </ins>количество типов монет. Также заметим, что <tex>E = M \times 2 + E^*</tex>, где <tex>E^*</tex> <ins class="diffchange diffchange-inline">– </ins>общее минимальное <ins class="diffchange diffchange-inline">число </ins>монет, которые нужно получить все коллекционерам (кроме вас), чтобы вступить в клуб <tex>+</tex> сумма типов монет, которых больше <tex>1</tex>, по всем коллекционерам. Из всего этого следует, что итоговое время работы будет <tex>O(ME)</tex></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== См.также ==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== См.также ==</div></td></tr>
</table>176.59.22.229http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=59539&oldid=prevKarenkovID в 09:39, 10 января 20172017-01-10T09:39:55Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 09:39, 10 января 2017</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l53" >Строка 53:</td>
<td colspan="2" class="diff-lineno">Строка 53:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сначала проверим, что <tex>2 \times B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой <tex>A</tex>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> — величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> — общее количество испорченных клеток.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> — величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f \times A+(K-f) \times B</tex>, где <tex>K</tex> — общее количество испорченных клеток.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">===Доказательство корректности===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Заметим следующее: по сути мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот - это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером <tex>2 \times 1</tex> и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>KarenkovIDhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%81%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B0&diff=59538&oldid=prevKarenkovID в 09:29, 10 января 20172017-01-10T09:29:16Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 09:29, 10 января 2017</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l61" >Строка 61:</td>
<td colspan="2" class="diff-lineno">Строка 61:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>===Решение===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Файл:Coints_task.gif|300px|thumb|right|Жёлтые вершины - монеты разных типов, синие - коллекционеры. Красное ребро означает, что коллекционеру нужна монета этого типа, зелёное - что у него больше одной монеты данного типа]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Файл:Coints_task.gif|300px|thumb|right|Жёлтые вершины - монеты разных типов, синие - коллекционеры. Красное ребро означает, что коллекционеру нужна монета этого типа<ins class="diffchange diffchange-inline">, причём пропускная способнасть этого ребра равна 1</ins>, зелёное - что у него больше одной монеты данного типа]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Построим сеть следующего вида: создадим для каждого типа монет по одной вершине, эти вершины будут соответствовать вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности <tex>1</tex> в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более <tex>k-1</tex> монеты, которых у него <tex>k (k > 1)</tex>. Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности <tex>1</tex> из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью <tex>k_i - 1</tex> в вершину <tex>i</tex>, соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Построим сеть следующего вида: создадим для каждого типа монет по одной вершине, эти вершины будут соответствовать вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности <tex>1</tex> в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более <tex>k-1</tex> монеты, которых у него <tex>k (k > 1)</tex>. Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности <tex>1</tex> из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью <tex>k_i - 1</tex> в вершину <tex>i</tex>, соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">===Доказательство корректности===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Как уже было сказано, построенная сеть отражает процессы обмена в клубе, пример можно посмотреть на картинке выше. Заметим следующее: </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* из вершины каждого типа монет может выйти поток, величина которого <tex><= 1 </tex></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* в вершины каждого типа монет может войти поток, величина которого не больше количества монет данного типа</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* если коллекционеру нужна эта монета и мы решили дать её, то мы дадим максимум одну монету этого типа, т.к. пропускная способность красного ребра <tex>= 1</tex>.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* если в данную вершину пришёл поток данной величины, то мы должны отдать из этой вершины поток такой же величины. (Из определения потока)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Всё вышесказанное подтверждает то, что построенная сеть корректно отображает процессы обмена монетами между участниками.    </ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=== Оценка времени работы ===</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>KarenkovID