#include "dec_menu.c"
char improvement1(double **x,double **x0,double **d,int imax,int jmax,int M,int N)
{
 int i,j,i1,j1,k;
 char fl,plus;
 int **x1;
 int *index1,*index2;
 double min=100000.0;
 index1 = new int [M];
 index2 = new int [N];
 x1 = new int* [M];
 for(i=0;i<M;i++)
 {
  x1[i] = new int [N];
  for(j=0;j<N;j++) x1[i][j] = 0;
 }

 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(x0[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(x0[i][j] && index1[i]) k++;
    if(k<2) fl = index2[j] = 0;
   }
  if(fl) break;
 }
 i1=imax;
 j=j1=jmax;
 if(!x[i1][j1]) plus = 1;
  else plus = 0;
 while(1)
 {
  for(i=0;i<M;i++)
   if(x0[i][j1] && index1[i] && i!=i1)
    {
     plus = (plus+1)%2;
     if(plus) x1[i][j1] = 2;
      else x1[i][j1] = -2;
     i1 = i;
     break;
 	}
  for(j=0;j<N;j++)
   if(x0[i1][j] && index2[j] && j!=j1)
      {
       plus = (plus+1)%2;
       if(plus) x1[i1][j] = 2;
       else x1[i1][j] = -2;
       j1 = j;
       break;
      }
 if(i1==imax && j1==jmax) break;
 }
 for(i=0;i<M;i++)
 {
  for(j=0;j<N;j++)
  {
   if(x1[i][j] == 2)
    min = minimum(d[imax][jmax],d[i][j]-x[i][j],min);
   if(x1[i][j] == -2)
    min = minimum(d[imax][jmax],x[i][j],min);
   if(!min) break;
  }
  if(!min) break;
 }
 if(!min)
 {
  x0[i][j]=0;
 }
  else
 {
  for(i=0;i<M;i++)
  for(j=0;j<N;j++)
  {
   if(x1[i][j] == -2) x[i][j] -= min;
   if(x1[i][j] == 2) x[i][j] += min;
  }
  for(i=0;i<M;i++)
  for(j=0;j<N;j++) x0[i][j] = 0;
  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 ;
   }
  }
 }
 for(i=0;i<M;i++) delete x1[i];
 delete x1;
 delete index1;
 delete index2;
 return 0;
}
