На этом шаге рассмотрим реализацию процедуры инициализации нулевого потока.

Procedure Init;
var i,j:integer;
begin 
  for i:=0 to Finish do 
    for j:=0 to Finish do f[i,j]:=0; 
  for i:=0 to Finish do 
    for j:=0 to Finish do cf[i,j]:=c[i,j]; 
  {построение списков входящих дуг} 
  for i:=0 to Finish do kia[i]:=0; 
  for i:=0 to Finish do {По всем вершинам} 
    for j:=1 to Finish do ia[i,j]:=-1; {no всем исходящим дугам} 
  for i:=0 to Finish do {По всем вершинам} 
    for j:=1 to ka[i] do {no всем исходящим дугам} 
    begin 
      inc(kia[a[i,j]]); {инкремент количества дуг, входящих в a[i,j]} 
      ia[a[i,j],kia[a[i,j]]]:=i; {запоминаем вершину i, как входящую в a[i,j]} 
    end;
end;

Вначале строится нулевой поток

for i:=0 to Finish do 
   for j:=0 to Finish do f[i,j]:=0;

Затем — начальная остаточная пропускная способность

for i:=0 to Finish do 
   for j:=0 to Finish do cf[i,j]:=c[i,j];

Далее для более удобной работы с "обратными" дугами увеличивающего пути строится "инвертированный" граф таким образом, что номера вершин в "инвертированном" графе остаются прежними, а направления дуг меняются на противоположные. Тем самым мы для каждой вершины получаем список входящих в нее дуг:

kia[i] — количество дуг, входящих в вершину i
ia[i,j] — номер вершины, из которой ведет j-я по счету дуга, входящая в вершину i

for i:=0 to Finish do kia[i]:=0; 
for i:=0 to Finish do {По всем вершинам} 
   for j:=1 to Finish do ia[i,j]:=-1; {no всем исходящим дугам}

Величины ia[i,j] инициализируются значением -1, поскольку нулем инициализировать нельзя — в графе есть дуги, исходящие из вершины 0.

На следующем шаге рассмотрим функцию ExistPath.

Предыдущий шаг Содержание Следующий шаг