#include "dec_menu.c"
void improvement(double **x,int imax,int jmax,int M,int N)
{
 int i,j,imin,jmin,tmp;
 char fl = 1,fl_zero=1;
 char *index1,*index2;
 double min = 100000.0;
 index1 = new char [M];
 index2 = new char [N];
 tmp = 0;
 for(i=0;i<M;i++) index1[i] = 1;
 for(i=0;i<N;i++) index2[i] = 1;
 while(fl)
 {
  fl = 0;
  for(i=0;i<M;i++) 
  {
   if(!index1[i]) continue;
   for(j=0;j<N;j++) if(x[i][j]&&index2[j]) tmp++;
   if(tmp < 2) index1[i] = 0,fl = 1;
   tmp = 0;
  }
  for(i=0;i<N;i++) 
  {
   if(!index2[i]) continue;
   for(j=0;j<M;j++) if(x[j][i]&&index1[j]) tmp++;
   if(tmp < 2) index2[i] = 0,fl = 1;
   tmp = 0;
  }
 }
 for(i=0;i<M;i++) if((i != imax)&&x[i][jmax]&&index1[i]) break;
 if(x[i][jmax] < min) 
 {
  min = x[i][jmax];
  if(fl_zero&&min == -2)
  {
   fl_zero = 0;
   imin = i;
   jmin = jmax;
  }
 }
 j = jmax;
 while(1)
 {
  for(tmp=0;tmp<N;tmp++) if((tmp != j)&&x[i][tmp]&&index2[tmp]) break;
  j = tmp;
  if(j == jmax) break;
  for(tmp=0;tmp<M;tmp++) if((tmp != i)&&x[tmp][j]&&index1[tmp]) break;
  i = tmp;
  if(x[i][j] < min)
  {
   min = x[i][j];
   if(fl_zero&&min == -2)
   {
	fl_zero = 0;
	imin = i;
	jmin = j;
   }
  }
  if(i == imax) break;
 }
 if(min == -2)
 {
  x[imin][jmin] = 0;
  x[imax][jmax] = min;
  return;
 }
 fl_zero = 1;
 for(i=0;i<M;i++) if((i != imax)&&x[i][jmax]&&index1[i]) break;
 j = jmax;
 x[i][j] -= min;
 if(!x[i][j]) fl_zero = 0;
 while(1)
 {
  for(tmp=0;tmp<N;tmp++) if((tmp != j)&&x[i][tmp]&&index2[tmp]) break;
  j = tmp;
  if(x[i][j] == -2) x[i][j] = min;
  else x[i][j] += min;
  if(j == jmax) break;
  for(tmp=0;tmp<M;tmp++) if((tmp != i)&&x[tmp][j]&&index1[tmp]) break;
  i = tmp;
  x[i][j] -= min;
  if(!x[i][j]&&!fl_zero) x[i][j] = -2;
  else if(fl_zero&&!x[i][j]) fl_zero = 0; 
  if(i == imax) break;
 }
 x[imax][jmax] = min;
 delete index1;
 delete index2;
}
