#include "declare.c"
void main(void)
{
 FILE *f;
 int i,j,k,imax,jmax,N,M,count;
 double tmp,tmp1,tmp2;
 double *a,*b,*v,*u;
 double **c,**x;
 f = fopen("input.dat","r");
 fscanf(f,"%d %d",&M,&N);
 a = new double [M+1];
 b = new double [N+1];
 u = new double [M+1];
 v = new double [N+1];
 x = new double* [M+1];
 c = new double* [M+1];
 for(i=0;i<M+1;i++)
 {
  x[i] = new double [N+1];
  c[i] = new double [N+1];
 }
 for(i=0;i<M;i++)
 for(j=0;j<N;j++)
 {
  fscanf(f,"%lf ",&tmp1);
  c[i][j] = tmp1;
 }
 count = tmp1 = tmp2 = 0;
 for(i=0;i<M;i++)
 {
  fscanf(f,"%lf ",&tmp);
  a[i] = tmp;
  tmp1 += a[i];
 }
 for(i=0;i<N;i++)
 {
  fscanf(f,"%lf ",&tmp);
  b[i] = tmp;
  tmp2 += b[i];
 }
 fclose(f);
 fflush(stdin);
 if(tmp1 > tmp2)
 {
  puts(" Внимание!      \nТранспортная задача открытого типа");
  puts(" Будет введен фиктивный пункт потребления");
  b[N] = tmp1-tmp2;
  puts("Введите коэффициенты штрафа с[i][N+1]:");
  for(i=0;i<M;i++)
  {
   scanf("%lf",&tmp);
   c[i][N] = tmp;
  }
  N++;
 }
 if(tmp1 < tmp2)
 {
  puts(" Внимание!      \nТранспортная задача открытого типа");
  puts(" Будет введен фиктивный пункт производства");
  a[M] = tmp2-tmp1;
  puts("Введите коэффициенты штрафа с[M+1][i]:");
  for(i=0;i<N;i++)
  {
   scanf("%lf",&tmp);
   c[M][i] = tmp;
  }
  M++;
 }
 nord_west(x,a,b,M,N);
 while(1)
 {
  poten(c,x,v,u,M,N);
  k = imax = jmax = 0;
  for(i=0;i<M;i++)
  for(j=0;j<N;j++)
  if((!x[i][j])&&(v[j]-u[i] > c[i][j])) k = 1;
  if(k)
  {
   for(i=0;i<M;i++)
   for(j=0;j<N;j++)
   if((v[jmax]-u[imax]-c[imax][jmax]) < (v[j]-u[i]-c[i][j]))
   {
    imax = i;
    jmax = j;
   }
  }
  else
  {
   puts(" Искомый план транспортной задачи");
   for(i=0;i<M;i++)
   {
    for(j=0;j<N;j++) if(x[i][j] == -2) printf("0.0 ");
                     else printf("%.1lf ",x[i][j]);
    puts("");
   }
   printf("Решение получено за %3d итераций\n",count);
   return;
  }
  if(Kofp)
  {
   puts(" потенциалы:");
   for(i=0;i<M;i++) printf("%.1lf ",u[i]);
   puts("");
   for(i=0;i<N;i++) printf("%.1lf ",v[i]);
   puts("\nПромежуточный план :");
   for(i=0;i<M;i++)
   {
    for(j=0;j<N;j++) if(x[i][j] == -2)printf("+0.0 ");
                     else printf("%.1lf ",x[i][j]);
    puts("");
   }
   printf(" %d %d count = %d \n",imax,jmax,count);
   for(k=i=0;i<M;i++)
   for(j=0;j<N;j++) if(x[i][j]>0) k++;
   if(k < N+M-1) puts(" Транспортная задача вырождена ");
   getch();
  }
  x[imax][jmax] = -1.0;
  improvement(x,imax,jmax,M,N);
  count++;
 }
 for(i=0;i<M;i++)
 {
  delete x[i];
  delete c[i];
 }
 delete x;
 delete c;
 delete a;
 delete b;
 delete v;
 delete u;
}
