[densi2009]

Привет всем. Помогите доделать программу. Очень надо.
требуется реализовать эти процедуры в программу, где вход Stringgrid1, а выход StringGrid2


Поиск максимального потока можно осуществлять с помощью алгоритмов Форда-Фалкерсона и Эдмондса-Карпа. Оба алгоритма основаны на методе Форда-Фалкерсона и отличаются только способом поиска дополняющей (S, T)-цепи. Предоставим сначала реализацию метода Форда-Фалкерсона, а процедуры поиска дополняющих цепей рассмотрим с каждым из алгоритмов отдельно.

Вход: G = (V, E, c) — сеть, заданная матрицей пропускных способностей M[1..n, 1..n].

Выход: максимальный поток f, заданный матрицей F[1..n, 1..n], для которой F[v, w] = f(v, w), | f | — величина максимального потока.

Код:

procedure MaximumFlow(M[1..n, 1..n])
1.  begin
2.    for (v из V)
3.      for (w из V)
4.        F[v][w] := 0;
5.    |f| := 0;
6.    do
7.      FindAugmentingPath();            //поиск дополняющей цепи
8.      if (h[T] < INF)
9.      then begin
10.       |f| := |f| + h[T];
11.       v := T;
12.       while (v != S) do   
13.       begin
14.         w := Previous[v];
15.         if (M[v, w] > 0)
16.           then F[v, w] := F[v, w] + h[T]; //прямая дуга — увеличиваем поток
17.           else F[v, w] := F[v, w] - h[T]; //обратная дуга — уменьшаем поток
18.         v := w;
19.       end
20.     end
21.    while (h[T] != INF);
22. end

Комментарий
Строки 2–5 — подготовка к алгоритму. Изначально потоки по всем дугам равны нулю и величина потока тоже равна нулю.
Строки 6–21 — основной цикл метода. Выполняется, пока существует дополняющая (S, T)-цепь.
Строка 7 — вызов метода поиска дополняющей (S, T)-цепи (реализация зависит от алгоритма).
Строка 8 — проверка: была ли найдена дополняющая цепь. В случае если такая цепь найдена, необходимо увеличить поток (строки 8–20).
Строки 8–20 — увеличение значения потока (строка 10) и изменение величин потоков на дугах в зависимости от их направленности (строки 12–19).
Алгоритм Форда-Фалкерсона

В алгоритме Форда-Фалкерсона поиск дополняющей цепи не регламентирован, поэтому можно умышленно выбирать такие дополняющие цепи, чтобы время работы алгоритма не зависело от размера задачи. Приведенная далее реализация была придумана специально, чтобы наглядно показать недостатки алгоритма. В ней используется модифицированный поиск в глубину.
В строке 7 выбор узла подобран так, чтобы время работы на первом примере зависела от пропускных способностей дуг.

Код:

procedure FindAugmentingPath() 
1.  begin
2.    for (v из V) do h[v] := INF;        
3.    Stack := NULL; Stack <- S; Previous[S] := NULL;
4.    while ((h[t] = INF) && (Stack != NULL))
5.    begin
6.      w <- Stack;
7.      for (v из V) do
8.        if (h[v] = INF)
9.        then begin 
10.           if (M[w, v] > 0)        //прямая дуга
11.           then
12.             if (M[w, v] > F[w, v])
13.             then begin
14.                 h[v] := MIN(h[w], M[w, v] - F[w, v]);
15.                 Previous[v] := w; Stack <- w; Stack <- v; 
16.                 BREAK;
17.               end
18.           if (M[w, v] < 0)        //обратная дуга
19.           then
10.             if (F[w, v] > 0)
21.             then begin
22.                 h[v] := MIN(h[w], F[w, v]);
23.                 Previous[v] := w; Stack <- w; Stack <- v; 
24.                 BREAK;
25.               end
26.         end
27.   end 
28. end

Комментарий
h() — вспомогательный массив. Если h[v] < INF, то существует ненасыщенная (S, v)-цепь, поток по которой можно увеличить на h[v].
Строки 2–3 — подготовка к поиску. Поиск всегда начинается из источника, поэтому добавляем его в стек.
Строки 4–27 — основной цикл. Выполняется поиск в глубину до тех пор, пока стек не пуст или пока сток не посещен. Строка 6 — извлекаем узел из стека, начинаем поиск в глубину из этого узла.
Строка 8 — проверка: была ли вершина посещена. В случае если вершину v посетили, то h[v] < INF.
Строки 15 и 23 — выполняется запись узла, из которого пришли в данный узел, чтобы потом восстановить цепочку, и добавляем узлы в стек для продолжения поиска в глубину.
Алгоритм Эдмондса-Карпа

В алгоритме Эдмондса-Карпа ведется поиск кратчайшей по числу дуг дополняющей (S, T)-цепи. Для поиска такой цепи лучше всего использовать поиск в ширину.

Код:

procedure FindAugmentingPath() 
1.  begin
2.    for (v из V) do h[v] := INF;
3.    Queue := NULL; Queue <- S; Previous[S] := NULL;
4.    while ((h[t] = INF) && (Queue != NULL)) do
5.    begin
6.      w <- Queue;
7.      for (v из V) do
8.        if (h[v] = INF)
9.        then begin
10.           if (M[w, v] > 0)        //прямая дуга
11.           then
12.             if (M[w, v] > F[w, v])
13.             then begin
14.                 h[v] := MIN(h[w], M[w, v] - F[w, v]);
15.                 Previous[v] := w; Queue <- v; 
16.               end
17.           if (M[w, v] < 0)        //обратная дуга
18.           then
19.             if (F[w, v] > 0)
20.             then begin
21.                 h[v] := MIN(h[w], F[w, v]);
22.                 Previous[v] := w; Queue <- v; 
23.               end
24.         end
25.   end  
26. end

Admin: Пользуемся тегами!

Комментарий
h() — вспомогательный массив. Если h[v] < INF, то существует ненасыщенная (S, v)-цепь, поток по которой можно увеличить на h[v].
Строки 2–3 — подготовка к поиску. Поиск всегда начинается из источника, поэтому добавляем его в очередь.
Строки 4–27 — основной цикл. Выполняется поиск в глубину до тех пор, пока очередь не пуста или пока сток не посещен.
Строка 6 — извлекаем узел из очереди, начинаем поиск в ширину из этого узла.
Строка 8 — проверка: была ли вершина посещена. В случае если вершину v посетили, то h[v] < INF.
Строки 15 и 22 — выполняется запись узла, из которого пришли в данный узел, чтобы потом восстановить цепочку, и добавляем узел в очередь для продолжения поиска в ширину.

[densi2009]

как пишутся эти строчки
2. for (v из V)
3. for (w из V)