TForm1 *Form1;
int N,M;//Размерность задачи
float *a;  //адрес массива запасов поставщиков
float *b;  //адрес массива потребностей потребителей
float **C; //адрес массива(двумерного) стоимости перевозки
float **X;//адрес массива(двумерного) плана доставки
float *u;//адрес массива потенциалов поставщиков
float *v;//адрес массива потенциалов потребителей
float **D;//адрес массива(двумерного) оценок свободных ячеек таблицы
bool stop;//признак достижения оптимального плана
bool **T;//массив будет хранить коодинаты ячеек, в коорые уже вписывались



   //--------------------------Метод потенциалов






            float find1,find2;//величина перераспределения поставки для цикла
            float best1=0;//наилучшая оценка улучшения среди всех допустимых перераспределений
            float best2=0;
            int ib1=-1;
            int jb1=-1;
            int ib2=-1;
            int jb2=-1;
            //Ищем наилучший цикл перераспределения поставок:
            for(int i=0;i<N;i++)
             for(int j=0;j<M;j++)
              if(D[i][j]<0)//Идём по ВСЕМ ячейкам с отрицательной оценкой
                {  //и ищем допустимые циклы перераспределения ДЛЯ КАЖДОЙ такой ячейки
                    //Обнуляем матрицу Y:
                    for(int i=0;i<N;i++)
                     for(int j=0;j<M;j++)
                       Y[i][j]=0;
                    //Ищем цикл для ячейки с оценкой D[i][j]:
                    find1=find_gor(i,j,i,j,N,M,X,Y,0,-1);//Начинаем идти по горизонтали

                     //Обнуляем матрицу Y:
                    for(int i=0;i<N;i++)
                     for(int j=0;j<M;j++)
                       Y[i][j]=0;
                    find2=find_ver(i,j,i,j,N,M,X,Y,0,-1);//Начинаем по вертикали

                    if(find1>0)
                      if(best1>D[i][j]*find1)
                         {
                            best1=D[i][j]*find1;//наилучшая оценка
                            ib1=i;//запомминаем координаты ячейки
                            jb1=j;//цикл из которой даёт наибольшее улучшение
                         }
                    if(find2>0)
                      if(best2>D[i][j]*find2)
                         {
                            best2=D[i][j]*find2;//наилучшая оценка
                            ib2=i;//запомминаем координаты ячейки
                            jb2=j;//цикл из которой даёт наибольшее улучшение
                         }
                 }
             if((best1==0)&&(best2==0))
             {
               //stop=true;
               //ShowMessage("Цикл перераспределения поставок не найден");
               ok=false;
               d=d1;//откат назад
               for(int i=0;i<N;i++)
                for(int j=0;j<M;j++)
                  if(X[i][j]==0)X[i][j]=-1;
               continue;
             }
            else
            {   //Обнуляем матрицу Y:
                for(int i=0;i<N;i++)
                     for(int j=0;j<M;j++)
                       Y[i][j]=0;
               //возвращаемся к вычислению цикла с наилучшим перераспределением:
               int ib,jb;
               if(best1<best2)
                   {
                     find_gor(ib1,jb1,ib1,jb1,N,M,X,Y,0,-1);
                     ib=ib1;
                     jb=jb1;
                   }
               else
                   {
                      find_ver(ib2,jb2,ib2,jb2,N,M,X,Y,0,-1);
                      ib=ib2;
                      jb=jb2;
                   }
               for(int i=0;i<N;i++)
                {
                  for(int j=0;j<M;j++)
                   {
                    if( (X[i][j]==0)&&(Y[i][j]<0) )
                       {
                         stop=true;
                         ok=false;
                         d=d1;//откат назад
                         Memo1->Lines->Add("Попытка отрицательной поставки!");
                         //ShowMessage("Попытка отрицательной поставки!");
                         //break;
                        }
                    X[i][j]= X[i][j]+Y[i][j];//перераспределяем поставки
                    if((i==ib)&&(j==jb))X[i][j]=X[i][j]+1;//добавляем 1 (т.к. до этого было -1 )
                    if((Y[i][j]<=0)&&(X[i][j]==0))X[i][j]=-1;//если ячейка обнулилась, то выбрасываем её из рассмотрения
                   }
                  //if(stop)break;
                }
              }
           //
          Memo1->Lines->Add("Матрица цикла перерасчёта:");
          Memo1->Lines->Add("");
          for(int i=0;i<N;i++)
           for(int j=0;j<M;j++)
            {
              Memo1->Text=Memo1->Text+FloatToStr(Y[i][j])+"    ";
              if(j==M-1)Memo1->Lines->Add("");
             }
           Memo1->Lines->Add("--------");
           //ShowMessage("Для продолжения нажмите "ОК" ");

          Memo1->Lines->Add("Новый план:");
          Memo1->Lines->Add("");
          float F=0;
          for(int i=0;i<N;i++)
           for(int j=0;j<M;j++)
            {
              Memo1->Text=Memo1->Text+FloatToStr(X[i][j])+"    ";
              if(X[i][j]>0)F=F+X[i][j]*C[i][j];
              if(j==M-1)Memo1->Lines->Add("");
             }
           Memo1->Lines->Add("F="+FloatToStr(F));
           Memo1->Lines->Add("--------");
           ShowMessage("Для продолжения нажмите "ОК" ");
           //

           ok=true;
           for(int i=0;i<N;i++)
             for(int j=0;j<M;j++)
               T[i][j]=false;


            delete []Y;

            //проверка на вырожденность: (?)
           L=0;
           for(int i=0;i<N;i++)
             for(int j=0;j<M;j++)
               if(X[i][j]>=0)L++;//подсчёт заполненных ячеек
            d=M+N-1-L;//если d>0,то задача - вырожденная
            d1=d;
            if(d>0)ok=false;

          }

          delete []u;
          delete []v;
          delete []ub;
          delete []vb;
          delete []D;


       }while(stop==false);

     Memo1->Lines->Add("Оптимальный план:");
     Memo1->Lines->Add("");
     float Fmin=0;
     for(int i=0;i<N;i++)
          for(int j=0;j<M;j++)
            {
              Memo1->Text=Memo1->Text+FloatToStr(X[i][j])+"    ";
              if(X[i][j]>0)Fmin=Fmin+X[i][j]*C[i][j];
              if(j==M-1)Memo1->Lines->Add("");
             }
     Memo1->Lines->Add("Fmin="+FloatToStr(Fmin));

      delete []X;
      delete []C;
      delete []a;
      delete []b;
}
//---------------------------------------------------------------------------
     //Функуция поиска ячеек,подлежащих циклу перераспределения (вдоль строки)
float TForm1::find_gor(int i_next,int j_next,int im,int jm,int n,int m,float** X,float** Y,int odd,float Xmin)
{
   int rez=-1;
   for(int j=0;j<m;j++)//идём вдоль строки, на которой стоим
 //ищем заполненную ячейку(кроме той,где стоим) или начальная ячейка(но уже в конце цикла:odd!=0 )
     if(((X[i_next][j]>=0)&&(j!=j_next))||((j==jm)&&(i_next==im)&&(odd!=0)))
       {
         odd++;//номер ячейки в цикле перерасчёта(начало с нуля)
         if(odd>1000)
           {
              ShowMessage("Угроза переполнения стека");
              return -1;
           }
         int Xmin_old=-1;
         if((odd%2)==1)//если ячейка нечётная в цикле ( начальная- нулевая )
          {
           Xmin_old=Xmin;//Запоминаем значение минимальной поставки в цикле (на случай отката назад)
           if(Xmin<0)Xmin=X[i_next][j];//если это первая встреченная ненулевая ячейка
           else if((X[i_next][j]<Xmin)&&(X[i_next][j]>=0))
                     {
                       Xmin=X[i_next][j];

                     }
          }
         if((j==jm)&&(i_next==im)&&((odd%2)==0))//если замкнулся круг и цикл имеет чётное число ячеек
           {
             Y[im][jm]= Xmin;//Значение минимальной поставки, на величину которой будем изменять
             return Xmin;
            }
           //если круг еще не замкнулся - переходим к поиску по вертикали:
         else rez=find_ver(i_next,j,im,jm,n,m,X,Y,odd,Xmin);//рекурсивный вызов
         if(rez>=0)//как бы обратный ход рекурсии(в случае если круг замкнулся)
            {
              //для каждой ячейки цикла заполняем матрицу перерасчёта поставок:
              if(odd%2==0)Y[i_next][j]=Y[im][jm];//в чётных узлах прибавляем
              else  Y[i_next][j]=-Y[im][jm];//в нечётных узлах вычитаем
              break;
            }
         else //откат назад в случае неудачи(круг не замкнулся):
           {
             odd--;
             if(Xmin_old>=0)//если мы изменяли Xmin на этой итерации
                Xmin=Xmin_old;
           }
       }

   return rez;//если круг замкнулся (вернулись в исходную за чётное число шагов) -
   // возвращает найденное минимальное значение поставки в нечётных ячейках цикла,
   // если круг не замкнулся, то возвращает -1.
}
//-----------------------------------------------------------------------------
    //Функуция поиска ячеек,подлежащих циклу перераспределения (вдоль столбца)
float TForm1::find_ver(int i_next,int j_next,int im,int jm,int n,int m,float** X,float** Y,int odd,float Xmin)
{
   int rez=-1;
   int i;
   for(i=0;i<n;i++)//идём вдоль столбца, на котором стоим
 //ищем заполненную ячейку(кроме той,где стоим) или начальная ячейка(но уже в конце цикла:odd!=0 )
     if(((X[i][j_next]>=0))&&(i!=i_next)||((j_next==jm)&&(i==im)&&(odd!=0)))
       {
         odd++;//номер ячейки в цикле перерасчёта(начало с нуля)
         if(odd>1000)
           {
              ShowMessage("Угроза переполнения стека");
              return -1;
           }
         int Xmin_old=-1;
         if((odd%2)==1)//если ячейка нечётная в цикле ( начальная- нулевая )
          {
            Xmin_old=Xmin;//Запоминаем значение минимальной поставки в цикле (на случай отката назад)
            if(Xmin<0)Xmin=X[i][j_next];//если это первая встреченная ненулевая ячейка
            else if((X[i][j_next]<Xmin)&&(X[i][j_next]>=0))
                       Xmin=X[i][j_next];


          }
         if((i==im)&&(j_next==jm)&&((odd%2)==0))//если замкнулся круг и цикл имеет чётное число ячеек
            {
              Y[im][jm]= Xmin;//Значение минимальной поставки, на величину которой будем изменять
              return Xmin;
            }
            //если круг еще не замкнулся - переходим к поиску по горизонтали:
         else rez=find_gor(i,j_next,im,jm,n,m,X,Y,odd,Xmin);//- рекурсивный вызов
         if(rez>=0)//как бы обратный ход (в случае если круг замкнулся)
            {
              //для каждой ячейки цикла заполняем матрицу перерасчёта поставок:
              if(odd%2==0)Y[i][j_next]=Y[im][jm];//эти прибавляются
              else  Y[i][j_next]=-Y[im][jm];//эти вычитаются
              break;
            }
         else //откат назад в случае неудачи (круг не замкнулся):
           {
             odd--;
             if(Xmin_old>=0)//если мы изменяли Xmin на этой итерации
                Xmin=Xmin_old;
           }
       }

   return rez;
}