|
Название: Графы(максимальный поток или максимальное паросочетание) Отправлено: fantomart от Декабрь 12, 2011, 09:49 Здравствуйте. Есть на выбор две задачи, "Максимальный поток" и "Максимальное паросочетание".
У меня есть вариант проекта qt, где реализован поиск в глубину. Нужно переделать этот проект под одну из этих двух задач. Условия задач: 1) Максимальное паросочетание Рассмотрим задачу о максимальном паросочетании в двудольном графе: есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны ли они друг другу. Нужно поженить максимальное число пар со взаимной симпатией. 2) Максимальный поток Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока). Более подробные условия есть на wiki. Помогите, пожалуйста, переделать проект на одно из этих заданий, либо сделать новый. Очень нужно. Оплачу естественно. Ссылка на проект: http://rghost.ru/33839261 Заранее, спасибо. |