|
Название: Графы(максимальный поток или максимальное паросочетание) Отправлено: fantomart от Декабрь 08, 2011, 22:11 Здравствуйте. Есть на выбор две задачи, "Максимальный поток" и "Максимальное паросочетание".
У меня есть вариант проекта qt, где реализован поиск в глубину. Нужно переделать этот проект под одну из этих двух задач. Условия задач: 1) Максимальное паросочетание Рассмотрим задачу о максимальном паросочетании в двудольном графе: есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны ли они друг другу. Нужно поженить максимальное число пар со взаимной симпатией. 2) Максимальный поток Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока). Более подробные условия есть на wiki. Помогите, пожалуйста, переделать проект на одно из этих заданий, либо сделать новый. Очень нужно. Ссылка на мой проект: http://rghost.ru/33839261 Заранее, спасибо. Название: Re: Графы(максимальный поток или максимальное паросочетание) Отправлено: LisandreL от Декабрь 09, 2011, 08:05 1) http://e-maxx.ru/algo/kuhn_matching
2) http://e-maxx.ru/algo/dinic http://e-maxx.ru/algo/preflow_push http://e-maxx.ru/algo/edmonds_karp Название: Re: Графы(максимальный поток или максимальное паросочетание) Отправлено: Igors от Декабрь 09, 2011, 13:23 И заданы две вершины: сток и исток. /offtopА где затвор? (как на половых транзисторах) Название: Re: Графы(максимальный поток или максимальное паросочетание) Отправлено: fantomart от Декабрь 10, 2011, 14:29 Кто-нибудь, помогите пожалуйста, просто графику в qt вообще не знаю(
Название: Re: Графы(максимальный поток или максимальное паросочетание) Отправлено: e-maxx от Декабрь 13, 2011, 01:48 /offtop
извините, но долго смеялся: (как на половых транзисторах) |