|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
23.04.2014, 22:55 | #1 |
Регистрация: 09.04.2014
Сообщений: 4
|
Реализация алгоритма Форда-Фалкерсона
Ребят, помогите реализовать алгоритм нахождения максимального потока методом Форда- Фалкерсона на С++. Я нашел в нескольких книгах реализацию алгоритма на Pascal, там изложено все настолько замысловато, что своими силами преобразовать в С++ не получается.
Источник алгоритма изложен в книге Окулов С.М. "Программирование в алгоритмах" |
24.04.2014, 08:24 | #2 |
Форумчанин
Регистрация: 08.07.2010
Сообщений: 505
|
Темы дублируешь?
Хоть пример на паскале привел бы, а то пойди, найди книжку, разберись и сделай по быстрому. Давай уже сделай че нить для хип хопа.
Знающий не говорит, говорящий не знает (С) Лао Цзы
|
24.04.2014, 21:48 | #3 |
Регистрация: 09.04.2014
Сообщений: 4
|
Этот код представлен в учебнике Основная логика. Begin <ввод данных и инициализация переменных(Lg:=True) >; While Lg Do Begin FillChar(P,SizeOЈ(P),0); <процедура расстановки меток(Mark), если вершину t не смогли пометить, то Lg:=False; результат работы - значение Р (метки вершин) >; If Lg Then <процедура Stream(t) - изменение потока по дугам найденной цепочки от вершины-стока t до вершины-источника s; входные данные - массив Р, результат - измененный массив F>; End; <вывод потока F> ; End.(конец обработки) Уточним логику расстановки меток (не лучший вариант). Procedure Mark; Var M:Set Of 1. .N; i, 1 -.integer; Begin M: = [l..N]; (*Непросмотренные вершины. *} P[s,l]:=s;P[s,2]:=maxint;{*Присвоим метку вершине-источнику. *} l:=s; While (P[t,l]=O) And Lg Do Begin For i:=l To N Do {*Поиск непомеченной вершины. *} If (P[i,l]=0) And ((C[l,i]<>0) Or (C[i,l]<>0)) Then If F[l,i]<C[l,i] " Then Вед1п{*Дуга прямая?*) P[i,l]:=1; If P[l,2]<C[l,i]-F[l,i] Then P[i,2]:=P[1,2] Else P[i,2]:=C[l,i]-F[l,i]; End Else If F[i,l]>0 Then Вед1п(*Дуга обратная?*) P[i,l]:=-1; If P[l,2]<F[i,l] Then P[i,2]:=P[1,2] Else P[i,2]:=F[i,l]; End; M:=M- [1] ; { *Вершина с номером 1 просмотрена.*} 1 :=1; { *Находим помеченную и непросмотренную вершину. *} Repeat Inc(l) Until (1>N) Or ((P[l,l]<>0) And (1 In M) ) ; If 1>N Then Lg:=False; End; End; Логика изменения потока F имеет вид: Procedure Stream (q:Integer); Begin {*Определяем тип дуги - прямая или обратная, знак минус у номера вершины - признак обратной дуги. *} If P[q,l]>0 Then F[P[q,1],q]:=F[P[q,1],q]+Р[t,2] Else F[q,abs(P[q,l])]:=F[q,abs(P[q,l] ) ]-P[t,2]; If Abs(P[q,l])<>s Then Begin{*Если не вершина-источник, то переход к предыдущей вершине цепочки. *} q:=Abs(P[q,l]); Stream(q); End; End; |
25.04.2014, 10:27 | #4 |
Форумчанин
Регистрация: 08.07.2010
Сообщений: 505
|
1. Потрудись для начала заключить код в теги CODE
Знак "#" на форме редактирования. 2. Сделай начальные попытки написания кода на С++. 3. Если первые два пункта не устраивают, пиши в личку, обсудим цену.
Знающий не говорит, говорящий не знает (С) Лао Цзы
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Помогите реализовать метод Форда Фалкерсона | Clockgen | Помощь студентам | 3 | 23.04.2014 22:45 |
алгоритм форда-фалкерсона | qpuTuJlb | Общие вопросы Delphi | 0 | 21.06.2013 19:58 |
Алгоритм Форда-Фалкерсона (о максимальном потоке в графе) | Chudo4258 | Помощь студентам | 1 | 30.06.2010 10:21 |
алгоритм Форда-Фалкерсона | goldlider | Общие вопросы Delphi | 10 | 20.04.2010 17:41 |
метод форда-фалкерсона | Дима164 | Помощь студентам | 0 | 05.12.2009 19:16 |