Алгоритм Эдмондса-Карпа

//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
 
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
#include <stack.h>
#include <queue.h>
TForm1 *Form1;
const max=50;
TPoint koortoch[50];   //массив точек
int n; //счетчик текущей вершины
int versh=-1; //понадобиться нам для обработки различных ситуаций при нажатии мыши
int mas[50][50];
 
int ceK[50];
int cK;
int s1[50];
int stK;
 
queue <int> och;
int p;
 
PrS[50][50];//массив пропускных способностей ребер
Vp[50][50]; // величина потока каждого ребра
int MaxP = 0; // максимальный поток
int proverka;
 
int x_,y_; // вершины
 
 
void shirina(int v)
{
stK=0;
cK=0;
     for (int i=0;i<50;i++)
     {
      s1[i] = 0;
      ceK[i] = 0;
     }
 
int Flag[50];
      for (int i=0;i<50;i++)
     {Flag[i]=0;}
 
int p;
och.push(v);
   s1[stK] = v;
   stK++;
   Flag[v] = 1;
 
   while (och.size()>0)
   {
    p = och.front();
    och.pop();
 
    ceK[cK]=p;
    cK++;
 
 
          for (int i=1;i<n+1;i++)
         {
              if ((mas[p][i]==1)&&(Flag[i]==0))
              {
               och.push(i);
               s1[stK] = v;
               stK++;
               Flag[i] = 1;
              }
         }
    }
 
}
 
 
void max_potok(int x, int y)
{
 
int count; //счетчик ребер в обходе
int p,z, last, Potok, proverka;
 
 
int Prop[50];
int Flag[50][50];
for (int i=0;i<50;i++)
     {
     Prop[i] = 0;
     }
 
for(int i = 0; i<50; i++)
for(int j = 0; j<50; j++)
Flag[i][j] = 0;// пока все вершины не посещены
 
 
och.push(x);// заносим с очередь первоначальную вершину
p = och.front();
last = p;// считаем, что первая вершина является последней
 
while(MaxP <= 3)
{
 
   while(last != y)  // пока последняя вершина не будет искомой в поиске
  {
 
     for(int i = 1; i<n+1; i++)
    {
      if( (mas[p][i] == 1) && (Flag[p][i] == 0) ) // находим смежные непосещенные вершины
           if( PrS[p][i] > Vp[p][i]) // если пропускная способность больше величины потока
          {
           och.push(i);  // то заносим смежную вершину в очередь
           last = i;
           Flag[x][i] = 1; // посетили вершину
 
           Prop[i] = PrS[p][i]; //запоминаем пропускную способность ребер
           //count++;
 
          }
    }
 
     for(int i = 1; i<n+1; i++)
        if(Flag[p][i] != 0) // если все смежные вершины посещены
 
         och.pop();  // удаляем текущую вершину из очереди
         p = och.front();// теперь поиск в ширину будет начинаться со следующей
                         //в очереди вершине
 
  }
 
 
     // если в очередь занесли искомую вершину, то находим максимальный поток
     for(int j = 0; j < 50; j++)
        if(Prop[j] > Potok)
        Potok = Prop[j];
 
 
       for(int k = 0; k < n; k++)
           for(int l = 0; l < n; l++)
               if(Flag[k][l] == 1)
                  PrS[k][l] = Potok;// изменяем значение величины потока
 
 
     MaxP += Potok;  // изменяем максимальный поток
 
}
     if(MaxP>3)proverka = 0; else proverka = 1;
 
}
 
void __fastcall TForm1::Image1MouseDown(TObject *Sender,
      TMouseButton Button, TShiftState Shift, int X, int Y)
{
if (Button==0)//если нажата правая кнопка мыши
{
Image1->Canvas->Pen->Width = 10;//радиус наших шариков
Image1->Canvas->TextOut(X+15,Y,IntToStr(n+1)); //выводится созданный по счету шарик
koortoch[n]=Point(X,Y);    //массив точек
n++; //увеличиваем номер вершины
Form1->StringGrid1->ColCount=n+1;//количество столбцов матр. смежности увеличивается
Form1->StringGrid1->RowCount=n+1; //количество строк матр. смежности увеличивается
 
for(int i=0;i<=n;i++)//в цикле проставляем номера столбцов и строк
{
Form1->StringGrid1->Cells[0][i]=i;
Form1->StringGrid1->Cells[i][0]=i;
}
 
Image1->Canvas->Pen->Color = clBlue;//устанавливаем цвет вершин
Image1->Canvas->Ellipse(X,Y,X+10,Y+10); //рисуем эллипс
}
 
if (Button==1)//если нажата левая кнопка мыши
{
 if (versh==-1)//если пока не запомнили ни одну из вершин
  {
   for(int i=0;i<n;i++) //проверяем попал ли щелчок мыши на какую-то из вершин
    if (X<koortoch[i].x+10&&X>koortoch[i].x-10&&Y<koortoch[i].y+10&&Y>koortoch[i].y-10)
     {
     versh=i;//если попали, то запоминаем вершину по которой щелкнули
     break;
     }
  }
  else //если по одной из вершин уже раннее щелкнули(запомнили), то
  {
   int toversh=-1;
   for(int i=0;i<n;i++)//проверяем не попал ли щелчок на одну из вершин
    if (X<koortoch[i].x+10&&X>koortoch[i].x-10&&Y<koortoch[i].y+10&&Y>koortoch[i].y-10)
     {
     toversh=i;//если попал, то соединяем вершины
     break;
     }
   if ((toversh!=-1)&&(versh!=toversh))//если щелкнули сначала по одной, а потом по другой вершине
   {
   //по номеру вершины узнаем ее конкретные координаты x и y
  Image1->Canvas->MoveTo(koortoch[versh].x,koortoch[versh].y);
  Image1->Canvas->Pen->Width = 1;//ширина линии , которой соединяем вершины
//рисуем линию между вершинами по которым щелкнули мышкой
  Image1->Canvas->LineTo(koortoch[toversh].x,koortoch[toversh].y);
 
  //заполняем матрицу смежности:
  Form1->StringGrid1->Cells[versh+1][toversh+1]=1;
  Form1->StringGrid1->Cells[toversh+1][versh+1]=1;
  mas[versh+1][toversh+1]=1;
  mas[toversh+1][versh+1]=1;
 
  // заполняем пропускные способности рёбер
  PrS[versh+1][toversh+1]=1;
  PrS[toversh+1][versh+1]=1;
  // и величины потока рёбер
  Vp[versh+1][toversh+1] = 0;
  Vp[toversh+1][versh+1] = 0;
 
  versh=-1;
   }
  }
}
 
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::FormActivate(TObject *Sender)
{
Image1->Picture=NULL;
Image1->Canvas->Rectangle(0,0,Width,Height);
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::DeleteClick(TObject *Sender)
{
 Image1->Picture=NULL;
 Image1->Canvas->Rectangle(0,0,Width,Height);
 
 for(int i=0;i<n+1;i++)
 for(int j=0;j<n+1;j++)
 StringGrid1->Cells[j][i]=""; //в цикле очищаем матрицу смежности
 n=0;//обнуляем счетчик вершин
 Edit1->Text="";
 Edit2->Text="";
 Label1->Caption = "";
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::ExitClick(TObject *Sender)
{
Form1->Close();
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::CreateClick(TObject *Sender)
{
StringGrid1->Visible = true;
Image1->Visible = true;
Delete->Visible = true;
Edit1->Visible = true;
Edit2->Visible = true;
Button1->Visible = true;
Label1->Visible = true;
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button1Click(TObject *Sender)
{
x_ = StrToInt(Edit1->Text);
y_ = StrToInt(Edit2->Text);
max_potok(x_,y_);
if(proverka == 1)
Form1->Label1->Caption = "Можно, максимальный поток меньше трёх";
else Form1->Label1->Caption = "Нельзя, максимальный поток больше трёх";
}
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
void __fastcall TForm1::Edit1Click(TObject *Sender)
{
Edit1->Text="";
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Edit2Click(TObject *Sender)
{
Edit2->Text="";
}
//---------------------------------------------------------------------------