Файл: Курсач ебаный.docx

Сделать презентацию

Скачать файл (0,08Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 23.01.2025

Просмотров: 410

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Алгоритм Дейкстры.

1) J(е)£a(е) для любой дуги еÎе,

2) В сети (g,j) у любой вершины, кроме источника и стока, полустепень исхода равна полустепени захода. Число j(е) называется значением потока через дугу е.

Алгоритм нахождения максимального потока

Решение

Источники информации:

Снова танцы. На вечеринку приглашены n мальчиков и n девочек. Они хотят станцевать несколько раундов. В каждом раунде гости делятся на n танцующих пар. Каждый гость должен быть в некоторой паре, каждая пара должна состоять из одного мальчика и одной девочки. В каждом раунде каждый мальчик должен танцевать с другой девочкой. Некоторые мальчики и девочки не нравятся друг другу. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Аналогично каждая девочка может танцевать не более чем с k мальчиками, которые ей не нравятся. Имеется информация о том, нравятся ли друг другу i-ый мальчик и j-ая девочка (1 ≤ i, j ≤ n). Найти наибольшее количество раундов, которое можно станцевать на вечеринке.

Решение

Рассмотрим следующую задачу: могут ли танцы продолжаться в точности m раундов? Если мы сможем ответить на этот вопрос, то бинарным поиском найдем наибольшее m, для которого проведение танцев возможно. Построим граф, имеющий один исток и один сток (черные вершины). Красные вершины представляют мальчиков, серые – девочек. Если мальчик и девочка нравятся друг другу, то проведем между ними ребро единичной пропускной способности (на рисунке такими являются два ребра – верхнее и нижнее). Иначе добавим синие и зеленые вершины как показано на рисунке и установим пропускную способность ребер между соответствующими синими и зелеными вершинами равную 1. Синие и зеленые вершины образуют “защитный” уровень. Связь мальчиков с девочками, которые друг другу не нравятся, будет проходить по ребрам защитного уровня. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Установим пропускную способность ребер между красными и синими, зелеными и серыми вершинами равную k. Таким образом, между каждым мальчиком и каждой девочкой будет установлена связь через ребро либо напрямую, либо через вершины защитного уровня. Танцы должны продолжаться в точности m раундов. Установим пропускную способность ребер между истоком и красными вершинами, а также между серыми вершинами и стоком равную m. Находим максимальный поток в графе. Танцы могут продолжаться в точности m раундов тогда и только тогда, когда величина максимального потока будет равна n * m, где n – количество мальчиков.Источник: Севастопольская летняя школа по программированию, 2010, День 4