Реализация алгоритма Форда—Фалкерсона

//(C) Igor Kvasov
{поиск максимального потока методом Форда-Фалкерсона;
для поиска дополняющего пути используется поиск в ширину}
const
  maxn = 1000;
  infinity = maxlongint;
var
  n,m,vin,vout,i,u,v,w,head,tail,ans:longint;
  ne,p,flow:array[1..maxn]of longint;
  e,c,f:array[1..maxn,1..maxn]of longint;
  q:array[0..maxn]of longint;

begin
  read(n,m,vin,vout);
  for i:=1 to m do begin
    read(u,v,w);
    if c[v,u]=0 then begin
      inc(ne[u]); e[u,ne[u]]:=v;
      inc(ne[v]); e[v,ne[v]]:=u;
    end;
    c[u,v]:=w;
  end;
  repeat
    p[vout]:=-1;
    fillchar(flow,sizeof(flow),0);
    flow[vin]:=infinity;
    head:=0; tail:=1; Q[0]:=vin;
    while head<tail do begin
      u:=Q[head]; inc(head);
      for i:=1 to ne[u] do begin
        v:=e[u,i];
        if (c[u,v]-f[u,v]>0)and(flow[v]=0) then begin
          Q[tail]:=v; inc(tail);
          p[v]:=u;
          if c[u,v]-f[u,v]<flow[u] then flow[v]:=c[u,v]-f[u,v]
                                   else flow[v]:=flow[u];
          if v=vout then break;
        end;
      end;
    end;
    if p[vout]=-1 then break;
    u:=vout;
    while u<>vin do begin
      f[p[u],u]:=f[p[u],u]+flow[vout];
      u:=p[u];
    end;
    ans:=ans+flow[vout];
  until false;
  write(ans);
end.

Тестовый пример:

6
0 5
0 16 0 0 13 0
0 0 12 0 6 0
0 0 0 0 9 20
0 0 7 0 0 4
0 0 0 14 0 0
0 0 0 0 0 0
Результат: 23

const int MAX_VERTICES = 40;

int NUM_VERTICES;           // число вершин в графе
const int INFINITY = 10000; // условное число, обозначающее бесконечность

int f[MAX_VERTICES][MAX_VERTICES];  // f[i][j] - поток, текущий от вершины i к j
int c[MAX_VERTICES][MAX_VERTICES];  // c[i][j] - максимальная величина потока, способная течь по ребру (i,j)

// набор вспомогательных переменных, используемых функцией FindPath - обхода в ширину
int Flow[MAX_VERTICES];  // Flow - значение потока через данную вершину на данном шаге поиска
int Link[MAX_VERTICES];  // Link[i] хранит номер предыдущей вешины на пути i -> исток
int Queue[MAX_VERTICES]; // очередь
int QP, QC;              // QP - указатель начала очереди и QC - число эл-тов в очереди

// поиск пути, по которому возможно пустить поток алгоритмом обхода графа в ширину
// функция ищет путь из истока в сток, по которому еще можно пустить поток,
// считая вместимость ребера (i,j) равной c[i][j] - f[i][j]

int FindPath(int source, int target) // source - исток, target - сток
{
    QP = 0; QC = 1; Queue[0] = source;
    Link[target] = -1; 
    int i;
    int CurVertex;
    memset(Flow, 0, sizeof(int)*NUM_VERTICES); 
    Flow[source] = INFINITY; 
    while (Link[target] == -1 && QP < QC)
    {
        CurVertex = Queue[QP];
        for (i=0; i<NUM_VERTICES; i++)
        if ((c[CurVertex][i] - f[CurVertex][i])>0 && Flow[i] == 0)
        {
            Queue[QC] = i; QC++;
            Link[i] = CurVertex; 
            if (c[CurVertex][i]-f[CurVertex][i] < Flow[CurVertex])
               Flow[i] = c[CurVertex][i];
            else
               Flow[i] = Flow[CurVertex];
          }
      QP++;    

    }

    if (Link[target] == -1) return 0;
    CurVertex = target;
    while (CurVertex != source)
    {
        f[Link[CurVertex]][CurVertex] +=Flow[target];
        CurVertex = Link[CurVertex];
    }
    return Flow[target];
}

// основная функция поиска максимального потока
int MaxFlow(int source, int target) // source - исток, target - сток
{
    memset(f, 0, sizeof(int)*MAX_VERTICES*MAX_VERTICES); 
    int MaxFlow = 0;
    int AddFlow;
    do
    {
        AddFlow = FindPath(source, target);
        MaxFlow += AddFlow;
    } while (AddFlow >0);
    return MaxFlow;
}

int main()
{
    int source, target;
    scanf("%d", &NUM_VERTICES);
    scanf("%d %d", &source, &target);
    int i, j;
    for (i=0; i<NUM_VERTICES; i++)
       for (j=0; j<NUM_VERTICES; j++)
         scanf("%d",&c[i][j]);

    printf("%d", MaxFlow(source, target));
    return 0;
}