#include "dec_menu.c"
int transp1(double **c,double **x,double **d,int M,int N,double eps,char flag)
{
 extern char win[5][6];
 extern char Kofp,limit;
 extern char fl_cikl;
 FILE *f;
 int i,j,k,imax,jmax,count;
 double *v,*u,st,s1,mi;
 double **x0;
 fl_cikl = 0;
 x0 = new double* [M];
 for(i=0;i<M;i++)
 {
  x0[i] = new double [N];
  for(j=0;j<N;j++) x0[i][j] = 0;
 }
 u = new double [M];
 v = new double [N];
  k=0;
  for(i=0;i<M;i++)
  for(j=0;j<N;j++)
  {
   if( x[i][j]>0 && x[i][j]<d[i][j] )
    {
     x0[i][j] = 1;
     if( !cikl(x0,M,N) ) k++;
      else x0[i][j] = 0;
     if( k == M+N-1 ) break;
    }
   if( k == M+N-1 ) break;
  }

  while( k < M+N-1)
  {
   for(i=0;i<M;i++)
   {
    for(j=0;j<N;j++)
     if(!x0[i][j])
      {
       x0[i][j] = 1;
       if( !cikl(x0,M,N) ) k++;
    	else x0[i][j] = 0;
       if( k == M+N-1 ) break;
      }
    if( k == M+N-1 ) break ;
   }
  }
 count = 0;
 while(1)
 {
  mi = 0;
  if(fl_cikl || count > 2*M*N)
  {
   for(i=0;i<M;i++) delete x0[i];
   delete x0;
   delete v;
   delete u;
   if(flag) return -3;
   return count;
  }
  poten(c,x0,v,u,M,N);
  k = 0;
  for(i=0;i<M;i++)
  for(j=0;j<N;j++)
   if( ( (x[i][j]==0)&&(c[i][j]-v[j]+u[i]<0) ) ||
       ( (x[i][j]==d[i][j])&&(c[i][j]-v[j]+u[i]>0) ) )  k = 1;
  if(k)
  {
   for(i=0;i<M;i++)
   for(j=0;j<N;j++)
   {
    if(!x0[i][j])
    {
     if(x[i][j]==0)
      {
       s1 = c[i][j] - v[j] + u[i];
       if(s1 < mi) 
        {
         mi = s1;
         imax = i;
         jmax = j;
        }
      }
     if(x[i][j]==d[i][j])
      {
       s1 = c[i][j] - v[j] + u[i];
       if(-s1 < mi) 
        {
         mi = -s1;
         imax = i;
         jmax = j;
        }
      }
    } 
   }
  }
  else break;
  if(Kofp && !flag)
  {
   f = fopen("tmpfile.tmp","w");
   fputs(" потенциалы:\nu: ",f);
   for(i=0;i<M;i++) fprintf(f,"%.1lf ",u[i]);
   fputs("\nv: ",f);
   for(i=0;i<N;i++) fprintf(f,"%.1lf ",v[i]);
   fputs("\nПромежуточный план :\n",f);
   for(i=0;i<M;i++)
   {
    for(j=0;j<N;j++) fprintf(f,"%.1lf ",x[i][j]);
    fputs("\n",f);
   }
   fputs("\nБазисные перевозки :\n",f);
   st=0;
   for(i=0;i<M;i++)
   {
    for(j=0;j<N;j++)
		   {
		     st += x[i][j]*c[i][j];
		     if(x0[i][j] == 1) fprintf(f,"(%d,%d)\n",i,j);
		    }
   }
   fprintf(f," ведущий элемент %d %d \n count = %d \n",imax,jmax,count);
   fprintf(f," стоимость перевозок: %.2lf \n",st);
   fclose(f);
   maliar_space(win[2][0]+1,win[2][1]+1,win[2][2]-1,win[2][3]-1,win[2][4]);
   view(win[2][0],win[2][1],win[2][2],win[2][3],win[2][4]);
   maliar_space(win[2][0]+1,win[2][1]+1,win[2][2]-1,win[2][3]-1,win[2][4]);
  }
  x0[imax][jmax] = 1;
  if(improvement1(x,x0,d,imax,jmax,M,N) == 1)
  {
   message("внимание!","   Выбор базисных","  перевозок зациклился","     вот");
   fl_cikl = 1;
  }
  count++;
  if(flag && x[M-1][N-1]==eps)
  {
   for(i=0;i<M;i++) delete x0[i];
   delete x0;
   delete v;
   delete u;
   return -1;
  }
 }
 for(i=0;i<M;i++) delete x0[i];
 delete x0;
 delete v;
 delete u;
 if(flag)
 {
  if(x[N-1][M-1]==eps) return -1;
   else return -2;
 }
 return count;
}
//***********************************************************************
char cikl(double **x,int m,int n)
{
 char *index1,*index2;
 int i,j,k;
 char fl=1;
 index1 = new char [m];
 index2 = new char [n];
 for(i=0;i<m;i++) index1[i] = 1;
 for(i=0;i<n;i++) index2[i] = 1;
 while(1)
 {
  fl = 1;
  for(i=0;i<m;i++)
   if(index1[i])
   {
    k=0;
    for(j=0;j<n;j++)
     if(x[i][j] && index2[j]) k++;
    if(k<2) fl = index1[i] = 0;
   }
  for(j=0;j<n;j++)
   if(index2[j])
   {
    k=0;
    for(i=0;i<m;i++)
     if(x[i][j] && index1[i]) k++;
    if(k<2) fl = index2[j] = 0;
   }
  if(fl) break;
 }
 fl = 0;
 for(i=0;i<m;i++)
 for(j=0;j<n;j++) if(index2[j] && index1[i]) fl = 1;
 delete index1;
 delete index2;
 return fl;
}
