Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > C++ Builder
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 23.04.2014, 22:55   #1
Mastdrak
 
Регистрация: 09.04.2014
Сообщений: 4
По умолчанию Реализация алгоритма Форда-Фалкерсона

Ребят, помогите реализовать алгоритм нахождения максимального потока методом Форда- Фалкерсона на С++. Я нашел в нескольких книгах реализацию алгоритма на Pascal, там изложено все настолько замысловато, что своими силами преобразовать в С++ не получается.
Источник алгоритма изложен в книге Окулов С.М. "Программирование в алгоритмах"
Mastdrak вне форума Ответить с цитированием
Старый 24.04.2014, 08:24   #2
Krok27
Форумчанин
 
Аватар для Krok27
 
Регистрация: 08.07.2010
Сообщений: 505
По умолчанию

Темы дублируешь?
Хоть пример на паскале привел бы, а то пойди, найди книжку, разберись и сделай по быстрому. Давай уже сделай че нить для хип хопа.
Знающий не говорит, говорящий не знает (С) Лао Цзы
Krok27 вне форума Ответить с цитированием
Старый 24.04.2014, 21:48   #3
Mastdrak
 
Регистрация: 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;
Mastdrak вне форума Ответить с цитированием
Старый 25.04.2014, 10:27   #4
Krok27
Форумчанин
 
Аватар для Krok27
 
Регистрация: 08.07.2010
Сообщений: 505
По умолчанию

1. Потрудись для начала заключить код в теги CODE
Знак "#" на форме редактирования.

2. Сделай начальные попытки написания кода на С++.

3. Если первые два пункта не устраивают, пиши в личку, обсудим цену.
Знающий не говорит, говорящий не знает (С) Лао Цзы
Krok27 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите реализовать метод Форда Фалкерсона 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