#include <iostream.h>
#define TRUE 1
#define FALSE 0
typedef int Boolean;
#define MaxNodes 8
#define MaxInt 1000  //Машинный эквивалент бесконечности.
class Spisok
{
  private:
    int cap[MaxNodes][MaxNodes];  //Функция пропускной способности.
    int flow[MaxNodes][MaxNodes]; //Максимальная функция потока.
    Boolean Any (Boolean *);
  public:
    void Vvod();
    void Maxflow (int, int, int *);
    void Vyvod (int);
};

void main()
{
  Spisok A;
  int s;  //Источник.
  int t;  //Сток.
  int totflow; //Значение потока от узла s к узлу t.

  //Задайте пропускную способность.
  A.Vvod();
  cout << "Укажите источник... "; cin >> s;
  cout << "Укажите сток... "; cin >> t;
  //Вывод результатов.
  A.Maxflow (s,t,&totflow);
  A.Vyvod(totflow);
}

void Spisok::Vvod()
{
  for (int i=0;i<MaxNodes;i++)
   for (int j=0;j<MaxNodes;j++)
   {
     cout << "Введите элемент " << i << " " << j<< " ";
     cin >> cap[i][j];
   }
}

void Spisok::Vyvod(int totflow)
{
  for (int i=0;i<MaxNodes;i++)
  {
    for (int j=0;i<MaxNodes;i++)
      cout << flow[i][j] << " ";
    cout << endl;
  }
  cout << "Значение потока: " << totflow << endl;
}

Boolean Spisok::Any (Boolean *Q)
{
  Boolean A = FALSE;

  for (int i=0;i<MaxNodes;i++) A = (A || Q[i]);
  return A;
}

void Spisok::Maxflow (int s, int t, int *totflow)
{
  int nd,i,x,pred;
  Boolean endpath[MaxNodes];
  Boolean onpath[MaxNodes];
  Boolean forward[MaxNodes];
  int     improve[MaxNodes];
  int     precede[MaxNodes];

  for (nd=0;nd<MaxNodes;nd++)
   for (i=0;i<MaxNodes;i++)
            flow[nd][i] = 0;
  *totflow = 0;
  do {
    //Попытка найти полупуть из s в t.
    for (nd=0;nd<MaxNodes;nd++)
    {
      endpath[nd] = FALSE;
      onpath [nd] = FALSE;
    }
    endpath[s] = TRUE;
    onpath [s] = TRUE;
    improve[s] = MaxInt;
    // Мы допускаем, что s обеспечивает неопределенный поток.
    while  (!onpath[t] && Any (&endpath[0])) 
    {
      // Попытка расширить существующий путь.
      nd = 0;
      while (!endpath[nd]) nd++;
      endpath[nd] = FALSE;
      for (i=0;i<MaxNodes;i++)
      {
        if (flow[nd][i]<cap[nd][i] && !onpath[i])
        {
           endpath[i]  = TRUE;
           onpath [i]  = TRUE;
           precede[i]  = nd;
           forward[nd] = TRUE;
           x = cap[nd][i] - flow[nd][i];
           if  ( improve[nd]<x ) improve[i] = improve[nd];
           else  improve[i] = x;
        }
        if (flow[i][nd]>0 && !onpath[i])
        {
           onpath [i]  = TRUE;
           endpath[i]  = TRUE;
           precede[i]  = nd;
           forward[nd] = FALSE;
           if ( improve[nd]<flow[i][nd] )
                 improve[i] = improve[nd];
           else  improve[i] = flow[i][nd];
        }
      }
    }
    if ( onpath[t] )
    // Поток на полупути к t может быть увеличен.
    {
       x = improve[t];
       *totflow += x;
       nd = t;
       while ( nd!=s )
       // Возвращение обратно вдоль пути.
       {
          pred = precede [nd];
          if ( forward[pred] )
          // Увеличение потока от pred.
                flow[pred][nd] += x;
          else // Уменьшение потока от pred.
                flow[pred][nd] -= x;
          nd = pred;
       }
    }            
  } while ( onpath[t] );
}