// Maksymalny przepływ - algorytm Edmondsa-Karpa
// Data: 08.08.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

program maxflow;

// Definicja typu elementów listy
//-------------------------------
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push (v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.data;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push (v : integer);
var
  p : PslistEl;
begin
  new (p);
  p^.next := nil;
  p^.data := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose (p);
  end;
end;

//---------------
// Program główny
//---------------

var
  Q : queue;                      // Kolejka
  C : array of array of integer;  // Macierz przepustowości
  F : array of array of integer;  // Macierz przepływów netto
  P : array of integer;           // Tablica poprzedników
  CFP : array of integer;         // Tablica przepustowości rezydualnych
  n, m, s, t, fmax, cp, x, y, i, j : integer;  // Zmienne proste algorytmu
  esc : boolean;                  // Do wychodzenia z zagnieżdżonych pętli

begin
  Q.init;                         // Inicjujemy kolejkę

  // Ze standardowego wejścia odczytujemy
  // n - liczbę wierzchołków w grafie sieci
  // m - liczbę krawędzi

  read (n, m);

  // Tworzymy dynamicznie macierze:
  // C - przepustowości krawędzi
  // F - przepływy w krawędziach

  SetLength (C, n); SetLength (F, n);
  for i := 0 to n - 1 do
  begin
    SetLength (C [i], n);
    SetLength (F [i], n);
  end;

  // Tworzymy dynamicznie tablice:
  // P   - poprzedniki na ścieżkach tworzonych przez BFS
  // CFP - przepustowość ścieżek

  SetLength (P, n);
  SetLength (CFP, n);

  // Zerujemy macierze przepustowości i przepływów

  for i := 0 to n - 1 do
    for j := 0 to n - 1 do
    begin
      C [i][j] := 0;
      F [i][j] := 0;
    end;

  // Ze standardowego wejścia odczytujemy definicje krawędzi.
  // Każda definicja składa się z trzech liczb
  // x, y - wierzchołki grafu połączone krawędzią
  // cp  - przepustowość krawędzi
  // Odczytane dane zapamiętujemy: C [x][y] = cp

  for i := 1 to m do
  begin
    read (x, y, cp);
    C [x][y] := cp;
  end;

  // Na koniec odczytujemy numer wierzchołka źródła s
  // oraz numer wierzchołka ujścia t

  read (s, t);

  //**************************************************
  //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  //**************************************************

  // Rozpoczynamy od maksymalnego przepływu równego zero

  fmax := 0;

  // W pętli szukamy ścieżek rozszerzających dotąd,
  // dopóki istnieją w sieci rezydualnej. Każda znaleziona
  // ścieżka zwiększa przepływ wzdłuż zawartych w niej
  // krawędzi grafu sieci przepływowej

  while true do
  begin

    // Na początku pętli zerujemy tablicę poprzedników P

    for i := 0 to n - 1 do P [i] := -1;

    // źródło nie posiada poprzednika. Wpisujemy tutaj -2,
    // aby BFS nie wybierało źródła

    P [s] := -2;

    // Do CFP [s] wpisujemy największą liczbę całkowitą

    CFP [s] := MAXINT;

    // Zerujemy kolejkę i umieszczamy w niej źródło s

    while not Q.empty do Q.pop;
    Q.push (s);

    // Zmienna esc umożliwia odpowiednie wychodzenie z
    // dwóch zagnieżdżonych pętli - zamiast polecenie goto.

    esc := false;

    // Rozpoczynamy pętlę wyszukującą ścieżki BFS. Pętla kończy
    // się w przypadku braku dalszych wierzchołków w kolejce

    while not Q.empty do
    begin

      // Z początku kolejki pobieramy element i usuwamy go z kolejki

      x := Q.front; Q.pop;

      // Sprawdzamy wszystkich sąsiadów wierzchołka x przeglądając
      // wiersz macierzy C

      for y := 0 to n - 1 do
      begin

        // Dla sąsiada y wyznaczamy przepustowość rezydualną
        // krawędzi x->y. Jeśli krawędź nie istnieje w sieci,
        // to otrzymamy w cp wynik zero

        cp := C [x][y] - F [x][y];

        // Sprawdzamy, czy krawędź istnieje oraz czy wierzchołek
        // y nie był już wcześniej wybrany przez BFS. W takim
        // przypadku P [y] ma wartość różną od -1.

        if(cp <> 0) and (P [y] = -1) then
        begin

          // W P [y] zapamiętujemy, iż poprzednikiem y jest x

          P [y] := x;

          // Dla wierzchołka y obliczamy dotychczasową przepustowość
          // rezydualną ścieżki. Jest to mniejsza wartość z przepustowości
          // ścieżki dla poprzednika x i bieżącej przepustowości
          // rezydualnej krawędzi x->y.

          if CFP [x] > cp then CFP [y] := cp else CFP [y] := CFP [x];

          // Jeśli osiągnęliśmy ujście, to ścieżka jest kompletna

          if y = t then
          begin

            // Zwiększamy przepływ maksymalny o przepustowość rezydualną
            // ścieżki - wykorzystujemy tablicę CFP

            inc (fmax, CFP [t]);

            // Idziemy wstecz po ścieżce zwiększając przepływy
            // wzdłuż jej krawędzi w kierunku zgodnym ze ścieżką
            // oraz zmniejszając przepływy w kierunku przeciwnym

            i := y;
            while i <> s do
            begin
              x := P [i];
              inc (F [x][i], CFP [t]);
              dec (F [i][x], CFP [t]);
              i := x;
            end;

            // Ustawiamy esc na true, co spowoduje wyjście z obu pętli

            esc := true; break;

          end;

          // Jeśli wierzchołek y nie jest ujściem t, to dopisujemy
          // go na końcu kolejki Q i kontynuujemy pętlę BFS

          Q.push (y);

        end;
      end;

      // Tutaj wychodzimy z pętli while, jeśli
      // została znaleziona ścieżka rozszerzająca

       if esc then break;

    end;

    // Jeśli nie znaleziono ścieżki rozszerzającej, to esc = false
    // i w tym miejscu nastąpi wyjście z głównej pętli while

    if not esc then break;

  end;

  // Prezentujemy wyniki obliczeń. Najpierw wypisujemy
  // wartość maksymalnego przepływu

  writeln;
  writeln('fmax = ', fmax);
  writeln;

  // Następnie wypisujemy przepływy netto wzdłuż krawędzi

  for x := 0 to n - 1 do
    for y := 0 to n - 1 do
      if C [x][y] <> 0 then writeln(x, ' -> ', y, ' ', F [x][y], ':', C [x][y]);

  writeln;

  // Usuwamy zmienne dynamiczne

  for i := 0 to n - 1 do
  begin
    SetLength (C [i], 0);
    SetLength (F [i], 0);
  end;

  SetLength (C, 0);
  SetLength (F, 0);
  SetLength (P, 0);
  SetLength (CFP, 0);

  Q.destroy;

end.

// Maksymalny przepływ - algorytm Edmondsa-Karpa
// Data: 08.08.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu elementów listy
//-------------------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();  // konstruktor
    ~queue(); // destruktor
    bool empty (void);
    int  front (void);
    void push (int v);
    void pop (void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty (void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front (void)
{
  if(head) return head->data;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push (int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->data = v;
  if(tail) tail->next = p;
  else       head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop (void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  queue Q;   // Kolejka
  int ** C;  // Macierz przepustowości
  int ** F;  // Macierz przepływów netto
  int * P;   // Tablica poprzedników
  int * CFP; // Tablica przepustowości rezydualnych
  int n, m, s, t, fmax, cp, x, y, i, j; // Zmienne proste algorytmu
  bool esc;  // Do wychodzenia z zagnieżdżonych pętli

  // Ze standardowego wejścia odczytujemy
  // n - liczbę wierzchołków w grafie sieci
  // m - liczbę krawędzi

  cin >> n >> m;

  // Tworzymy dynamicznie macierze:
  // C - przepustowości krawędzi
  // F - przepływy w krawędziach

  C = new int * [n];
  F = new int * [n];
  for(i = 0; i < n; i++)
  {
    C [i] = new int [n];
    F [i] = new int [n];
  }

  // Tworzymy dynamicznie tablice:
  // P   - poprzedniki na ścieżkach tworzonych przez BFS
  // CFP - przepustowość ścieżek

  P = new int [n];
  CFP = new int [n];

  // Zerujemy macierze przepustowości i przepływów

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++) C [i][j] = F [i][j] = 0;

  // Ze standardowego wejścia odczytujemy definicje krawędzi.
  // Każda definicja składa się z trzech liczb
  // x, y - wierzchołki grafu połączone krawędzią
  // cp  - przepustowość krawędzi
  // Odczytane dane zapamiętujemy: C [x][y] = cp

  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> cp;
    C [x][y] = cp;
  }

  // Na koniec odczytujemy numer wierzchołka źródła s
  // oraz numer wierzchołka ujścia t

  cin >> s >> t;

  //**************************************************
  //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  //**************************************************

  // Rozpoczynamy od maksymalnego przepływu równego zero

  fmax = 0;

  // W pętli szukamy ścieżek rozszerzających dotąd,
  // dopóki istnieją w sieci rezydualnej. Każda znaleziona
  // ścieżka zwiększa przepływ wzdłuż zawartych w niej
  // krawędzi grafu sieci przepływowej

  while(true)
  {

    // Na początku pętli zerujemy tablicę poprzedników P

    for(i = 0; i < n; i++) P [i] = -1;

    // źródło nie posiada poprzednika. Wpisujemy tutaj -2,
    // aby BFS nie wybierało źródła

    P [s] = -2;

    // Do CFP [s] wpisujemy największą liczbę całkowitą

    CFP [s] = MAXINT;

    // Zerujemy kolejkę i umieszczamy w niej źródło s

    while(!Q.empty()) Q.pop();
    Q.push (s);

    // Zmienna esc umożliwia odpowiednie wychodzenie z
    // dwóch zagnieżdżonych pętli - zamiast polecenie goto.

    esc = false;

    // Rozpoczynamy pętlę wyszukującą ścieżki BFS. Pętla kończy
    // się w przypadku braku dalszych wierzchołków w kolejce

    while(!Q.empty())
    {

      // Z początku kolejki pobieramy element i usuwamy go z kolejki

      x = Q.front(); Q.pop();

      // Sprawdzamy wszystkich sąsiadów wierzchołka x przeglądając
      // wiersz macierzy C

      for(y = 0; y < n; y++)
      {

        // Dla sąsiada y wyznaczamy przepustowość rezydualną
        // krawędzi x->y. Jeśli krawędź nie istnieje w sieci,
        // to otrzymamy w cp wynik zero

        cp = C [x][y] - F [x][y];

        // Sprawdzamy, czy krawędź istnieje oraz czy wierzchołek
        // y nie był już wcześniej wybrany przez BFS. W takim
        // przypadku P [y] ma wartość różną od -1.

        if(cp && (P [y] == -1))
        {

          // W P [y] zapamiętujemy, iż poprzednikiem y jest x

          P [y] = x;

          // Dla wierzchołka y obliczamy dotychczasową przepustowość
          // rezydualną ścieżki. Jest to mniejsza wartość z przepustowości
          // ścieżki dla poprzednika x i bieżącej przepustowości
          // rezydualnej krawędzi x->y.

          CFP [y] = CFP [x] > cp ? cp : CFP [x];

          // Jeśli osiągnęliśmy ujście, to ścieżka jest kompletna

          if(y == t)
          {

            // Zwiększamy przepływ maksymalny o przepustowość rezydualną
            // ścieżki - wykorzystujemy tablicę CFP

            fmax += CFP [t];

            // Idziemy wstecz po ścieżce zwiększając przepływy
            // wzdłuż jej krawędzi w kierunku zgodnym ze ścieżką
            // oraz zmniejszając przepływy w kierunku przeciwnym

            i = y;
            while(i != s)
            {
              x = P [i];
              F [x][i] += CFP [t];
              F [i][x] -= CFP [t];
              i = x;
            }

            // Ustawiamy esc na true, co spowoduje wyjście z obu pętli

            esc = true; break;
          }

          // Jeśli wierzchołek y nie jest ujściem t, to dopisujemy
          // go na końcu kolejki Q i kontynuujemy pętlę BFS

          Q.push (y);
        }
      }

      // Tutaj wychodzimy z pętli while, jeśli
      // została znaleziona ścieżka rozszerzająca

       if(esc) break;
    }

    // Jeśli nie znaleziono ścieżki rozszerzającej, to esc = false
    // i w tym miejscu nastąpi wyjście z głównej pętli while

    if(!esc) break;
  }

  // Prezentujemy wyniki obliczeń. Najpierw wypisujemy
  // wartość maksymalnego przepływu

  cout << endl << "fmax = " << fmax << endl << endl;

  // Następnie wypisujemy przepływy netto wzdłuż krawędzi

  for(x = 0; x < n; x++)
    for(y = 0; y < n; y++)
      if(C [x][y]) cout << x << " -> " << y << " " << F [x][y] << ":" << C [x][y] << endl;

  cout << endl;

  // Usuwamy zmienne dynamiczne

  for(i = 0; i < n; i++)
  {
    delete [] C [i];
    delete [] F [i];
  }

  delete [] C;
  delete [] F;
  delete [] P;
  delete [] CFP;

  return 0;}

' Maksymalny przepływ - algorytm Edmondsa-Karpa
' Data: 08.08.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type slistEl
  next As slistEl Ptr
  data As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push (ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push (ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->data = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim As queue Q            ' Kolejka
Dim As Integer Ptr Ptr C  ' Macierz przepustowości
Dim As Integer Ptr Ptr F  ' Macierz przepływów netto
Dim As Integer Ptr P      ' Tablica poprzedników
Dim As Integer Ptr CFP    ' Tablica przepustowości rezydualnych
Dim As Integer n, m, s, t, fmax, cp, x, y, i, j ' Zmienne proste algorytmu
Dim As Byte esc           ' Do wychodzenia z zagnieżdżonych pętli

Open Cons For Input As #1

' Ze standardowego wejścia odczytujemy
' n - liczbę wierzchołków w grafie sieci
' m - liczbę krawędzi

Input #1, n, m

' Tworzymy dynamicznie macierze:
' C - przepustowości krawędzi
' F - przepływy w krawędziach

C = New Integer Ptr [n]
F = New Integer Ptr [n]
For i = 0 To n - 1
  C [i] = New Integer [n]
  F [i] = New Integer [n]
Next

' Tworzymy dynamicznie tablice:
' P   - poprzedniki na ścieżkach tworzonych przez BFS
' CFP - przepustowość ścieżek

P = New Integer [n]
CFP = New Integer [n]

' Zerujemy macierze przepustowości i przepływów

For i = 0 To n - 1
  For j = 0 To n - 1
  	 C [i][j] = 0
  	 F [i][j] = 0
  Next
Next

' Ze standardowego wejścia odczytujemy definicje krawędzi.
' Każda definicja składa się z trzech liczb
' x, y - wierzchołki grafu połączone krawędzią
' cp  - przepustowość krawędzi
' Odczytane dane zapamiętujemy: C [x][y] = cp

For i = 1 To m
  Input #1, x, y, cp
  C [x][y] = cp
Next

' Na koniec odczytujemy numer wierzchołka źródła s
' oraz numer wierzchołka ujścia t

Input #1, s, t

Close #1

'**************************************************
'** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
'**************************************************

' Rozpoczynamy od maksymalnego przepływu równego zero

fmax = 0

' W pętli szukamy ścieżek rozszerzających dotąd,
' dopóki istnieją w sieci rezydualnej. Każda znaleziona
' ścieżka zwiększa przepływ wzdłuż zawartych w niej
' krawędzi grafu sieci przepływowej

While 1

  ' Na początku pętli zerujemy tablicę poprzedników P

  For i = 0 To n - 1
  	 P [i] = -1
  Next

  ' źródło nie posiada poprzednika. Wpisujemy tutaj -2,
  ' aby BFS nie wybierało źródła

  P [s] = -2

  ' Do CFP [s] wpisujemy największą liczbę całkowitą

  CFP [s] = MAXINT

  ' Zerujemy kolejkę i umieszczamy w niej źródło s

  While Q.empty() = 0
  	 Q.pop()
  Wend
  Q.push (s)
 
  ' Zmienna esc umożliwia odpowiednie wychodzenie z
  ' dwóch zagnieżdżonych pętli - zamiast polecenie goto.

  esc = 0

  ' Rozpoczynamy pętlę wyszukującą ścieżki BFS. Pętla kończy
  ' się w przypadku braku dalszych wierzchołków w kolejce

  While Q.empty() = 0

    ' Z początku kolejki pobieramy element i usuwamy go z kolejki

    x = Q.front()
    Q.pop()

    ' Sprawdzamy wszystkich sąsiadów wierzchołka x przeglądając
    ' wiersz macierzy C

    For y = 0 To n - 1

      ' Dla sąsiada y wyznaczamy przepustowość rezydualną
      ' krawędzi x->y. Jeśli krawędź nie istnieje w sieci,
      ' to otrzymamy w cp wynik zero

      cp = C [x][y] - F [x][y]

      ' Sprawdzamy, czy krawędź istnieje oraz czy wierzchołek
      ' y nie był już wcześniej wybrany przez BFS. W takim
      ' przypadku P [y] ma wartość różną od -1.

      If cp <> 0 AndAlso P [y] = -1 Then

        ' W P [y] zapamiętujemy, iż poprzednikiem y jest x

        P [y] = x

        ' Dla wierzchołka y obliczamy dotychczasową przepustowość
        ' rezydualną ścieżki. Jest to mniejsza wartość z przepustowości
        ' ścieżki dla poprzednika x i bieżącej przepustowości
        ' rezydualnej krawędzi x->y.

        If CFP [x] > cp Then
        	 CFP [y] = cp
        Else
        	 CFP [y] = CFP [x]
        EndIf

        ' Jeśli osiągnęliśmy ujście, to ścieżka jest kompletna

        If y = t Then

          ' Zwiększamy przepływ maksymalny o przepustowość rezydualną
          ' ścieżki - wykorzystujemy tablicę CFP

          fmax += CFP [t]

          ' Idziemy wstecz po ścieżce zwiększając przepływy
          ' wzdłuż jej krawędzi w kierunku zgodnym ze ścieżką
          ' oraz zmniejszając przepływy w kierunku przeciwnym

          i = y
          While i <> s
            x = P [i]
            F [x][i] += CFP [t]
            F [i][x] -= CFP [t]
            i = x
          Wend

          ' Ustawiamy esc na true, co spowoduje wyjście z obu pętli

          esc = 1
          Exit For
        EndIf

        ' Jeśli wierzchołek y nie jest ujściem t, to dopisujemy
        ' go na końcu kolejki Q i kontynuujemy pętlę BFS

        Q.push (y)
      EndIf
    Next

    ' Tutaj wychodzimy z pętli while, jeśli
    ' została znaleziona ścieżka rozszerzająca

    If esc = 1 Then Exit While
  Wend

  ' Jeśli nie znaleziono ścieżki rozszerzającej, to esc = false
  ' i w tym miejscu nastąpi wyjście z głównej pętli while

  If esc = 0 Then Exit While
Wend

' Prezentujemy wyniki obliczeń. Najpierw wypisujemy
' wartość maksymalnego przepływu

Print
Print "fmax =";fmax
Print

' Następnie wypisujemy przepływy netto wzdłuż krawędzi

For x = 0 To n - 1
  For y = 0 To n - 1
    If C [x][y] <> 0 Then Print Using "& -> & &:&";x;y;F [x][y];C [x][y]
  Next
Next

Print

' Usuwamy zmienne dynamiczne

for i = 0 To n - 1
  Delete [] C [i]
  Delete [] F [i]
Next

Delete [] C
Delete [] F
Delete [] P
Delete [] CFP

End

// Maksymalny przepływ - algorytm Edmondsa-Karpa
// Data: 24.08.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

program maxflow;

// Definicja typu elementów listy
//-------------------------------
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    v, c, f : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
queue = object
  private
    head : PslistEl;
    tail : PslistEl;

  public
    constructor init;
    destructor  destroy;
    function    empty : boolean;
    function    front : integer;
    procedure   push (x : integer);
    procedure   pop;
end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push (x : integer);
  var
    p : PslistEl;
begin
  new (p);
  p^.next := nil;
  p^.v    := x;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
  var
    p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose (p);
  end;
end;

//---------------
// Program główny
//---------------

var
  m, n  : integer;           // Liczba krawędzi i wierzchołków w grafie
  L     : array of PslistEl; // Tablica list sąsiedztwa
  s, t  : integer;           // Numer wierzchołka źródła s i ujścia t
  fmax  : integer;           // Maksymalny przepływ sieciowy
  Q     : queue;             // Kolejka
  P     : array of integer;  // Tablica poprzedników
  CFP   : array of integer;  // Tablica przepustowości rezydualnych dla ścieżek
  i, cp, u, v : integer;     // Zmienne pomocnicze
  x, z  : PslistEl;          // Wskaźniki elementów listy sąsiedztwa
  test  : boolean;

begin

  Q.init;

  // Najpierw odczytujemy liczbę wierzchołków i krawędzi grafu

  read (n, m);

  // Tworzymy i inicjujemy struktury dynamiczne

  SetLength (L, n);           // Tablica wskaźników list
  for i := 0 to n - 1 do
    L [i] := nil;             // Tablicę wypełniamy pustymi listami

  SetLength (P, n);
  SetLength (CFP, n);

  // Teraz wczytujemy definicje poszczególnych krawędzi grafu.
  // Każda krawędź jest zdefiniowana przez trzy liczby u, v i cp:
  // u  - wierzchołek początkowy krawędzi
  // v  - wierzchołek końcowy krawędzi
  // cp - przepustowość krawędzi

  for i := 1 to m do
  begin
    // Najpierw odczytujemy te trzy liczby

    read (u, v, cp);

    // Tworzymy nowy element listy

    new (x);

    // Wypełniamy jego pola danych

    x^.v := v;
    x^.c := cp;
    x^.f := 0;                  // Zerujemy przepływ

    // Element dołączamy do listy sąsiadów wierzchołka u

    x^.next := L [u];
    L [u] := x;
  end;

  // Na koniec odczytujemy numery wierzchołków źródła i ujścia

  read (s, t);

  //**************************************************
  //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  //**************************************************

  // Zerujemy wartość maksymalnego przepływu sieciowego

  fmax := 0;

  // Tworzymy w grafie strukturę sieci rezydualnej

  for u := 0 to n - 1 do
  begin
    x := L [u];
    while x <> nil do
    begin
      // Sprawdzamy, czy na liście sąsiadów x jest wierzchołek u.
      // Jeśli tak, to krawędź zwrotna istnieje i nie ma potrzeby
      // jej tworzenia.

      test := false;            // Zakładamy brak krawędzi zwrotnej
      z := L [x^.v];
      while z <> nil do
      begin
        if z^.v = u then
        begin
          test := true; break;
        end;
        z := z^.next;
      end;

      if not test then          // Jeśli brak krawędzi, tworzymy ją
      begin
        new (z);
        z^.v := u;
        z^.c := 0;
        z^.f := 0;
        z^.next := L [x^.v];
        L [x^.v] := z;
      end;
      x := x^.next;
    end;
  end;

  // Sieć rezydualna została utworzona. Teraz zajmiemy się wyznaczeniem
  // maksymalnych przepływów w sieci.

  while true do
  begin
    for i := 0 to n - 1 do
      P [i] := -1;            // Zerujemy tablicę poprzedników

    CFP [s] := MAXINT;        // Przepustowość źródła jest nieskończona

    while not Q.empty do Q.pop; // Zerujemy kolejkę

    Q.push (s);               // W kolejce umieszczamy źródło s

    // Szukamy ścieżki w sieci rezudualnej od źródła s do ujścia t

    while not Q.empty do
    begin
      test := false;            // Zakładamy brak takiej ścieżki
      u := Q.front; Q.pop;      // Pobieramy wierzchołek z kolejki

      // Przeglądamy listę sąsiadów wierzchołka u

      x := L [u];
      while x <> nil do
      begin
        // Wyznaczamy przepustowość rezydualną kanału

        cp := x^.c - x^.f;

        // Przetwarzamy tylko istniejące i nieodwiedzone jeszcze krawędzie

        if(cp <> 0) and (P [x^.v] = -1) then
        begin
          // Zapamiętujemy poprzednik na ścieżce

          P [x^.v] := u;

          // Obliczamy przepustowość rezydualną do węzła x^.v

          if cp < CFP [u] then CFP [x^.v] := cp else CFP [x^.v] := CFP [u];

          // Sprawdzamy, czy ścieżka sięga do ujścia

          if x^.v = t then
          begin
            test := true;       // Sygnalizujemy znalezioną ścieżkę
            break;              // Wychodzimy z pętli for
          end
          else Q.push (x^.v); // Inaczej umieszczamy w kolejce wierzchołek x^.v
        end;

        x := x^.next;
      end;

      if test then break;   // Jeśli jest ścieżka, wychodzimy z pętli while
    end;

    if not test then break; // Jeśli brak ścieżki, kończymy algorytm

    // Zwiększamy przepływ sieciowy

    inc (fmax, CFP [t]);

    // Cofamy się po ścieżce od ujścia t do źródła s

    v := t;
    while v <> s do
    begin
      u := P [v];         // u jest poprzednikiem v na ścieżce

      // Szukamy na liście sąsiadów u krawędzi prowadzącej do v.

      z := L [u];
      while z <> nil do
      begin
        if z^.v = v then
        begin
          inc (z^.f, CFP [t]); // W kierunku zgodnym ze ścieżką zwiększamy przepływ
          break;
        end;
        z := z^.next;
      end;

      // Szukamy na liście sąsiadów v krawędzi prowadzącej do u.

      z := L [v];
      while z <> nil do
      begin
        if z^.v = u then
        begin
          dec (z^.f, CFP [t]); // W kierunku przeciwnym do ścieżki zmniejszamy przepływ
          break;
        end;
        z := z^.next;
      end;

      v := u;
    end;
  end;

  // Prezentujemy wyniki obliczeń. Najpierw wypisujemy
  // wartość maksymalnego przepływu

  writeln;
  writeln('fmax = ', fmax);
  writeln;

  // Następnie wypisujemy znalezione przez algorytm przepływy w
  // kanałach pierwotnej sieci przepływowej. Kanały rozpoznajemy
  // po niezerowej wartości ich przepustowości.

  for i := 0 to n - 1 do
  begin
    z := L [i];
    while z <> nil do
    begin
      if z^.c <> 0 then writeln(i, ' -> ', z^.v, ' ', z^.f, ':', z^.c);
      z := z^.next;
    end;
  end;
  writeln;

  // Koniec, usuwamy struktury dynamiczne

  for i := 0 to n - 1 do
  begin
    x := L [i];
    while x <> nil do
    begin
      z := x;
      x := x^.next;
      dispose (z);
    end;
  end;

  SetLength (L, 0);
  SetLength (P, 0);
  SetLength (CFP, 0);
  Q.destroy;

end.

// Maksymalny przepływ - algorytm Edmondsa-Karpa
// Data: 24.08.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu elementów listy
//-------------------------------
struct slistEl
{
  slistEl * next;
  int v, c, f;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty (void);
    int  front (void);
    void push (int v);
    void pop (void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty (void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front (void)
{
  if(head) return head->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push (int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v = v;
  if(tail) tail->next = p;
  else head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop (void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  int m, n;                    // Liczba krawędzi i wierzchołków w grafie
  slistEl ** L;                // Tablica list sąsiedztwa
  int s, t;                    // Numer wierzchołka źródła s i ujścia t
  int fmax;                    // Maksymalny przepływ sieciowy
  queue Q;                     // Kolejka
  int *P;                      // Tablica poprzedników
  int *CFP;                    // Tablica przepustowości rezydualnych dla ścieżek
  int i, cp, u, v;             // Zmienne pomocnicze
  slistEl *x, *z;              // Wskaźniki elementów listy sąsiedztwa
  bool test;

  // Najpierw odczytujemy liczbę wierzchołków i krawędzi grafu

  cin >> n >> m;

  // Tworzymy i inicjujemy struktury dynamiczne

  L = new slistEl * [n];     // Tablica wskaźników list
  for(i = 0; i < n; i++)
    L [i] = NULL;            // Tablicę wypełniamy pustymi listami

  P   = new int [n];
  CFP = new int [n];

  // Teraz wczytujemy definicje poszczególnych krawędzi grafu.
  // Każda krawędź jest zdefiniowana przez trzy liczby u, v i cp:
  // u  - wierzchołek początkowy krawędzi
  // v  - wierzchołek końcowy krawędzi
  // cp - przepustowość krawędzi

  for(i = 0; i < m; i++)
  {
    // Najpierw odczytujemy te trzy liczby

    cin >> u >> v >> cp;

    // Tworzymy nowy element listy

    x = new slistEl;

    // Wypełniamy jego pola danych

    x->v = v;
    x->c = cp;
    x->f = 0;                  // Zerujemy przepływ

    // Element dołączamy do listy sąsiadów wierzchołka u

    x->next = L [u];
    L [u] = x;
  }

  // Na koniec odczytujemy numery wierzchołków źródła i ujścia

  cin >> s >> t;

  //**************************************************
  //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  //**************************************************

  // Zerujemy wartość maksymalnego przepływu sieciowego

  fmax = 0;

  // Tworzymy w grafie strukturę sieci rezydualnej

  for(u = 0; u < n; u++)
  {
    for(x = L [u]; x; x = x->next)
    {
      // Sprawdzamy, czy na liście sąsiadów x jest wierzchołek u.
      // Jeśli tak, to krawędź zwrotna istnieje i nie ma potrzeby
      // jej tworzenia.

      test = false;            // Zakładamy brak krawędzi zwrotnej
      for(z = L [x->v]; z; z = z->next)
        if(z->v == u)
        {
          test = true; break;
        }
      if(test) continue;     // Jeśli jest krawędź, sprawdzamy kolejnego sąsiada

      // Tworzymy krawędź zwrotną

      z = new slistEl;
      z->v = u;
      z->c = z->f = 0;
      z->next = L [x->v];
      L [x->v] = z;
    }
  }

  // Sieć rezydualna została utworzona. Teraz zajmiemy się wyznaczeniem
  // maksymalnych przepływów w sieci.

  while(1)
  {
    for(i = 0; i < n; i++)
      P [i] = -1;                // Zerujemy tablicę poprzedników

    CFP [s] = MAXINT;            // Przepustowość źródła jest nieskończona

    while(!Q.empty()) Q.pop(); // Zerujemy kolejkę

    Q.push (s);                  // W kolejce umieszczamy źródło s

    // Szukamy ścieżki w sieci rezudualnej od źródła s do ujścia t

    while(!Q.empty())
    {
      test = false;             // Zakładamy brak takiej ścieżki
      u = Q.front(); Q.pop(); // Pobieramy wierzchołek z kolejki

      // Przeglądamy listę sąsiadów wierzchołka u

      for(x = L [u]; x; x = x->next)
      {
        // Wyznaczamy przepustowość rezydualną kanału

        cp = x->c - x->f;

        // Przetwarzamy tylko istniejące i nieodwiedzone jeszcze krawędzie

        if(cp && (P [x->v] == -1))
        {
          // Zapamiętujemy poprzednik na ścieżce

          P [x->v] = u;

          // Obliczamy przepustowość rezydualną do węzła x->v

          CFP [x->v] = cp < CFP [u] ? cp : CFP [u];

          // Sprawdzamy, czy ścieżka sięga do ujścia

          if(x->v == t)
          {
             test = true;       // Sygnalizujemy znalezioną ścieżkę
             break;             // Wychodzimy z pętli for
          }
          else Q.push (x->v); // Inaczej umieszczamy w kolejce wierzchołek x->v
        }
      }

      if(test) break;      // Jeśli jest ścieżka, wychodzimy z pętli while
    }

    if(!test) break;       // Jeśli brak ścieżki, kończymy algorytm

    // Zwiększamy przepływ sieciowy

    fmax += CFP [t];

    // Cofamy się po ścieżce od ujścia t do źródła s

    for(v = t; v != s; v = u)
    {
      u = P [v];           // u jest poprzednikiem v na ścieżce

      // Szukamy na liście sąsiadów u krawędzi prowadzącej do v.

      for(z = L [u]; z; z = z->next)
        if(z->v == v)
        {
          z->f += CFP [t]; // W kierunku zgodnym ze ścieżką zwiększamy przepływ
          break;
        }

      // Szukamy na liście sąsiadów v krawędzi prowadzącej do u.

      for(z = L [v]; z; z = z->next)
        if(z->v == u)
        {
          z->f -= CFP [t]; // W kierunku przeciwnym do ścieżki zmniejszamy przepływ
          break;
        }
    }
  }

  // Prezentujemy wyniki obliczeń. Najpierw wypisujemy
  // wartość maksymalnego przepływu

  cout << "\nfmax = " << fmax << endl << endl;

  // Następnie wypisujemy znalezione przez algorytm przepływy w
  // kanałach pierwotnej sieci przepływowej. Kanały rozpoznajemy
  // po niezerowej wartości ich przepustowości.

  for(i = 0; i < n; i++)
    for(z = L [i]; z; z = z->next)
      if(z->c)
        cout << i << " -> " << z->v << " " << z->f << ":" << z->c << endl;

  cout << endl;

  // Koniec, usuwamy struktury dynamiczne

  for(i = 0; i < n; i++)
  {
    x = L [i];
    while(x)
    {
      z = x;
      x = x->next;
      delete z;
    }
  }

  delete [] L;
  delete [] P;
  delete [] CFP;

  return 0;}

' Maksymalny przepływ - algorytm Edmondsa-Karpa
' Data: 24.08.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type slistEl
  next As slistEl Ptr
  v As Integer
  c As Integer
  f As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push (ByVal x As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return -1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push (ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head <> 0 Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim As Integer m, n          ' Liczba krawędzi i wierzchołków w grafie
Dim As slistEl Ptr Ptr L     ' Tablica list sąsiedztwa
Dim As Integer s, t          ' Numer wierzchołka źródła s i ujścia t
Dim As Integer fmax          ' Maksymalny przepływ sieciowy
Dim As queue Q               ' Kolejka
Dim As Integer Ptr P         ' Tablica poprzedników
Dim As Integer Ptr CFP       ' Tablica przepustowości rezydualnych dla ścieżek
Dim As Integer i, cp, u, v   ' Zmienne pomocnicze
Dim As slistEl Ptr x, z      ' Wskaźniki elementów listy sąsiedztwa
Dim As Integer test

' Najpierw odczytujemy liczbę wierzchołków i krawędzi grafu

Open Cons For Input As #1

Input #1, n, m

' Tworzymy i inicjujemy struktury dynamiczne

L = New slistEl Ptr [n]    ' Tablica wskaźników list
For i = 0 To n - 1
  L [i] = 0                ' Tablicę wypełniamy pustymi listami
Next

P = New Integer [n]
CFP = New Integer [n]

' Teraz wczytujemy definicje poszczególnych krawędzi grafu.
' Każda krawędź jest zdefiniowana przez trzy liczby u, v i cp:
' u  - wierzchołek początkowy krawędzi
' v  - wierzchołek końcowy krawędzi
' cp - przepustowość krawędzi

For i = 1 To m
  ' Najpierw odczytujemy te trzy liczby

  Input #1, u, v, cp

  ' Tworzymy nowy element listy

  x = New slistEl

  ' Wypełniamy jego pola danych

  x->v = v
  x->c = cp
  x->f = 0                   ' Zerujemy przepływ

  ' Element dołączamy do listy sąsiadów wierzchołka u

  x->next = L [u]
  L [u] = x
Next

' Na koniec odczytujemy numery wierzchołków źródła i ujścia

Input #1, s, t

'**************************************************
'** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
'**************************************************

' Zerujemy wartość maksymalnego przepływu sieciowego

fmax = 0

' Tworzymy w grafie strukturę sieci rezydualnej

For u = 0 To n - 1
  x = L [u]
  While x
    ' Sprawdzamy, czy na liście sąsiadów x jest wierzchołek u.
    ' Jeśli tak, to krawędź zwrotna istnieje i nie ma potrzeby
    ' jej tworzenia.

    test = 0                 ' Zakładamy brak krawędzi zwrotnej
    z = L [x->v]
    While z
      If z->v = u Then
        test = 1
        Exit While
      End If
      z = z->Next
    Wend

    If test = 0 Then         ' Jeśli brak krawędzi, tworzymy ją
      z = New slistEl
      z->v = u
      z->c = 0: z->f = 0
      z->next = L [x->v]
      L [x->v] = z
    End If
   
    x = x->Next
  Wend
Next

' Sieć rezydualna została utworzona. Teraz zajmiemy się wyznaczeniem
' maksymalnych przepływów w sieci.

While 1
  For i = 0 To n - 1
    P [i] = -1             ' Zerujemy tablicę poprzedników
  Next

  CFP [s] = MAXINT         ' Przepustowość źródła jest nieskończona

  While Not Q.empty()
    Q.pop()                 ' Zerujemy kolejkę
  Wend

  Q.push (s)               ' W kolejce umieszczamy źródło s

  ' Szukamy ścieżki w sieci rezudualnej od źródła s do ujścia t

  While Not Q.empty()
    test = 0                 ' Zakładamy brak takiej ścieżki
    u = Q.front(): Q.pop() ' Pobieramy wierzchołek z kolejki

    ' Przeglądamy listę sąsiadów wierzchołka u

    x = L [u]
    While x <> 0

      ' Wyznaczamy przepustowość rezydualną kanału

      cp = x->c - x->f

      ' Przetwarzamy tylko istniejące i nieodwiedzone jeszcze krawędzie

      if(cp <> 0) AndAlso (P [x->v] = -1) Then

        ' Zapamiętujemy poprzednik na ścieżce

        P [x->v] = u

        ' Obliczamy przepustowość rezydualną do węzła x->v

        If cp < CFP [u] Then
        	 CFP [x->v] = cp
        Else
        	 CFP [x->v] = CFP [u]
        EndIf

        ' Sprawdzamy, czy ścieżka sięga do ujścia

        If x->v = t Then
          test = 1            ' Sygnalizujemy znalezioną ścieżkę
          Exit While          ' Wychodzimy z pętli
        Else
          Q.push (x->v)     ' Inaczej umieszczamy w kolejce wierzchołek x->v
        End If
       
      End If
       
      x = x->Next
       
    Wend

    If test = 1 Then Exit While   ' Jeśli jest ścieżka, wychodzimy z pętli while
  Wend

  if test = 0 Then Exit While ' Jeśli brak ścieżki, kończymy algorytm

  ' Zwiększamy przepływ sieciowy

  fmax += CFP [t]

  ' Cofamy się po ścieżce od ujścia t do źródła s

  v = t
  While v <> s
    u = P [v]           ' u jest poprzednikiem v na ścieżce

    ' Szukamy na liście sąsiadów u krawędzi prowadzącej do v.

    z = L [u]
    While z
      If z->v = v Then
        z->f += CFP [t] ' W kierunku zgodnym ze ścieżką zwiększamy przepływ
        Exit While
      End If
      z = z->Next
    Wend

    ' Szukamy na liście sąsiadów v krawędzi prowadzącej do u.

    z = L [v]
    While z
      If z->v = u Then
        z->f -= CFP [t] ' W kierunku przeciwnym do ścieżki zmniejszamy przepływ
        Exit While
      End If
      z = z->Next
    Wend
     
    v = u
  Wend
   
Wend

' Prezentujemy wyniki obliczeń. Najpierw wypisujemy
' wartość maksymalnego przepływu

Print
Print "fmax =";fmax
Print

' Następnie wypisujemy znalezione przez algorytm przepływy w
' kanałach pierwotnej sieci przepływowej. Kanały rozpoznajemy
' po niezerowej wartości ich przepustowości.

For i = 0 To n - 1
  z = L [i]
  While z
    If z->c Then Print Using "& -> & &:&";i;z->v;z->f;z->c
    z = z->Next
  Wend
Next
Print

' Koniec, usuwamy struktury dynamiczne

For i = 0 To n - 1
  x = L [i]
  While x
    z = x
    x = x->Next
    Delete z
  Wend
Next

Delete [] L
Delete [] P
Delete [] CFP

End