 #include <stdio.h>
 #include <stdlib.h>

 #define NMAX 10
 #define MMAX 10
 #define CC 50

 #ifndef min
	#define min(a,b)  ((a)<(b) ? (a):(b))
 #endif

 void Zastavka( void);
 void Etap2(int i);
 float Zel_f(void);
 void Print_res( int ij, FILE *out);
 void Input ( void );
 int St( int k );
 void R_str (void );
 void R_st ( void);
 float New ( void);
 int Etap1( int p);
 void Etap3 ( void);
 void Etap0 ( void);
 int Uslovie3 ( void);

  float CK[MMAX][NMAX],C0[MMAX][NMAX],X0[MMAX][NMAX],C[MMAX][NMAX],Delta[NMAX],Delta_st[NMAX],Delta_str[MMAX],A[MMAX],B[NMAX];
  float S_str,S_st,L,ij;
  int Str_zv[MMAX],Str_sh[MMAX],min_str[NMAX],min_st[MMAX],n,m,c,N_str[CC],N_st[CC],Pr;
  char Metka_str[MMAX];

  void Input ( )
  {
   int	i,j;
   char file_name[14];
   FILE *in;

   printf( "Введите имя входного файла: ");
   scanf( "%13s", file_name);
   in=fopen( file_name,"r");
   fscanf(in,"%d%d",&m,&n);
   if((m>MMAX)||(n>NMAX)) exit(1);
   for(i=0;i<m;i++) fscanf(in,"%f",&A[i]);
   for(j=0;j<n;j++) fscanf(in,"%f",&B[j]);
   for(i=0;i<m;i++)
	for(j=0;j<n;j++)
	 fscanf(in,"%f",&C[i][j]);

   for (i=0;i<m;i++)
   for (j=0;j<n;j++)
    CK[i][j]=C[i][j];

   fclose(in);
 }

 float Zel_f( )
 {
  float summa;
  int i,j;

  summa=0;
  for(i=0;i<m;i++)
   for(j=0;j<n;j++)
	summa+=CK[i][j]*X0[i][j];
  return(summa);
 }

 void Print_res( int ij, FILE *out )
 {
  int i,j;

if(ij>=0)
 {
  fprintf( out,"	*************Итерация N %2d*************\n",ij);
  fprintf( out,"	Матрица транспортных издержек С0 : \n");
  for(i=0;i<m;i++)
   {
    fprintf( out,"%3d |",i);
    for(j=0;j<n;j++)
     fprintf( out,"%5f |",C0[i][j]);
    fprintf( out,"\n");
   }

  fprintf( out,"	План перевозок (матрица X0) : \n");
   for(i=0;i<m;i++)
   {
    fprintf( out,"%3d |",i);
    for(j=0;j<n;j++)
     fprintf( out,"%5f |",X0[i][j]);
    fprintf( out,"\n");
   }
  fprintf( out,"	Оценка целевой функции: %5f\n\n",L);
 } else
 {
  fprintf( out,"	*************Итерация N %2d*************\n",-ij);
  fprintf( out,"	Матрица транспортных издержек С0 : \n");
  for(i=0;i<m;i++)
   {
    fprintf( out,"%3d |",i);
    for(j=0;j<n;j++)
     fprintf( out,"%5f |",C0[i][j]);
    fprintf( out,"\n");
   }

  fprintf( out,"	Оптимальный план перевозок (матрица X0) : \n");
   for(i=0;i<m;i++)
   {
    fprintf( out,"%3d |",i);
    for(j=0;j<n;j++)
     fprintf( out,"%5f |",X0[i][j]);
    fprintf( out,"\n");
   }
  fprintf( out,"	Значение целевой функции: %5f\n\n",L);
 }
}

   int St( int k )
  { int i;
   for (i=0;i<m;i++)
    if (Str_zv[i]==k) return(i);
   return(-1);
  }

  void R_str ( )
  { int i,j;
    float summa;

    for (i=0;i<m;i++)
    { summa=0.0;
	  for (j=0;j<n;j++)
       summa+=X0[i][j];
      Delta_str[i]=A[i]-summa;
    }
  }

  void R_st ( )
  { int i,j;
    float summa;

    for (j=0;j<n;j++)
    { summa=0.0;
      for (i=0;i<m;i++)
	   summa+=X0[i][j];
      Delta_st[j]=B[j]-summa;
      Delta[j]=Delta_st[j];
    }
  }

  float New ( )
  {
   int S,S1,i,j;

   S=0;
   for (i=0;i<m;i++)
   S+=A[i];
   for (j=0;j<n;j++)
   S+=B[j];
   S1=0;
   for (i=0;i<m;i++)
    for (j=0;j<n;j++)
     S1+=X0[i][j];
   return(S-2*S1);
   }

   int Uslovie3 ( )
   {
    int count,i,j;
    count=0;
    for (j=0;j<n;j++)
	if ((Delta_st[j]==-1)||(Delta_st[j]>0))
     for (i=0;i<m;i++)
     if(Delta_str[i]!=0)
      if (C0[i][j]==0) count++;
     return(count);
    }


 int Etap1 ( int p)
  {
   int i,j,k;
   for (j=p;j<n;j++)
    if ((Delta_st[j]==-1)||(Delta_st[j]>0))
	 for (i=0;i<m;i++)
      if (Metka_str[i]=='-')
       if (C0[i][j]==0)
	{
	 Str_sh[i]=j;
	 if ( Delta_str[i]!=0)
	 {
		Etap2( i );
		return (1);
	 }
	 Metka_str[i]='+';
	 for (k=0;k<n;k++)
	  if ((Delta_st[k]==0)&&(X0[i][k]>0))
	   {
		Delta_st[k]=-1;
		Str_zv[i]=k;
		p=k;
		if(Etap1(p)==1) return(1);
	   }
	 }
	 return(0);
     }


void Etap3 ( )
{
 float h;
 int i,j;
 h=100;
 for (j=0;j<n;j++)
  if ((Delta_st[j]==-1)||(Delta_st[j]>0))
  for (i=0;i<m;i++)
   if (Metka_str[i]=='-')
    if (C0[i][j]<=h) h=C0[i][j];
 for (j=0;j<n;j++)
  for (i=0;i<m;i++)
   if (Metka_str[i]=='-') C0[i][j]=C0[i][j]-h;
 for (j=0;j<n;j++)
  if (Delta_st[j]==0)
   for (i=0;i<m;i++) C0[i][j]=C0[i][j]+h;
 }

 void Etap2 ( int i )
 {
  int R,j,J,I;
  float M_zv,Tetta;

  Pr=1;
  for (j=0;j<CC;j++) { N_str[j]=-1;N_st[j]=-1;}
  J=0; I=i;
  for (j=0;j<CC;j+=2)
  {
     N_str[j]=i;
     R=Str_sh[i];
     N_st[j]=R;
     J++;
	 i=St(R);
     if(i==-1) break;
     N_str[j+1]=i;
     N_st[j+1]=R;
     J++;
   }
  if(J>1)
  {
   M_zv=X0[N_str[1]][N_st[1]];
   for (j=1;j<J;j++)
    if ((Str_zv[N_str[j]]==N_st[j])&&(M_zv>X0[N_str[j]][N_st[j]]))
	M_zv=X0[N_str[j]][N_st[j]];
   Tetta=min(M_zv,min(Delta_str[I],Delta[N_st[J-1]]));
  }
  else Tetta=min(Delta_str[I],Delta[N_st[J-1]]);
  for (j=0;j<J;j++)
   if ( Str_sh[N_str[j]]==N_st[j] ) X0[N_str[j]][N_st[j]]+=Tetta;
    else  X0[N_str[j]][N_st[j]]-=Tetta;
 }

 void Etap0 ( )
 { int i,j,t;
   float S_str,S_st,razn,razn1;
  for (i=0;i<m;i++)
   for (j=0;j<n;j++)
    CK[i][j]=C[i][j];

  for (i=0;i<m;i++) min_str[i]=0;
  for (j=0;j<n;j++) min_st[j]=0;
  for (j=0;j<n;j++)
	for (i=0;i<m;i++)
	 if ( C[i][j]<C[min_st[j]][j]) min_st[j]=i;
 for (j=0;j<n;j++)
  {
   razn=C[min_st[j]][j];
   for (i=0;i<m;i++)
	C[i][j]-=razn;
   }
  for (i=0;i<m;i++)
   for (j=0;j<n;j++)
	if (C[i][j]<C[i][min_str[i]]) min_str[i]=j;
 for (i=0;i<m;i++)
  { razn1=C[i][min_str[i]];
	for (j=0;j<n;j++)
	C0[i][j]=C[i][j]-razn1;
  }
	for (i=0;i<m;i++)
	 {
	  if (C0[i][0]!=0) X0[i][0]=0;
	  else {
	  S_st=B[0];
	  for (t=0;t<i;t++) S_st-=X0[t][0];
	  if ( A[i]<S_st ) X0[i][0]=A[i];
	  else X0[i][0]=S_st;}
	 }

   for (j=1;j<n;j++)
	for (i=0;i<m;i++)
	 {
	  if (C0[i][j]!=0) X0[i][j]=0;
	  else {
			 S_str=A[i];S_st=B[j];
			 for (t=0;t<j;t++) S_str-=X0[i][t];
			 for (t=0;t<i;t++) S_st-=X0[t][j];
			 if ( S_str<S_st ) X0[i][j]=S_str;
			 else  X0[i][j]=S_st;
		   }
	 }
  }

 void Zastavka()
 {
     printf( "\t		     НГТУ\n\n\n");
     printf( "\t	 Кафедра прикладной математики\n\n\n");
     printf( "\t	       Курсовой проект\n");
     printf( "\t\"Венгерский метод решения транспортной задачи\"\n\n\n\n");
     printf( "\tФакультет: ФПМИ\n\n");
     printf( "\tГруппа	 : АП-11\n\n");
     printf( "\tСтудентка: Сазонова И.А.\n\n\n\n");
     printf( "\t		    1995г.\n\n\n\n");

 }

 void main ( )
 {
	int	d,Pr;
	char	file_name[14];
	FILE	*out;

   Zastavka();
   ij=0;
   Input( );
   printf( "Введите имя выходного файла: ");
   scanf( "%13s", file_name);
   out = fopen( file_name, "w");

   Etap0( );
   do
   { ij++;
     R_st( );R_str( );
     for (d=0;d<MMAX;d++) { Metka_str[d]='-';Str_sh[d]=-1;Str_zv[d]=-1;}
	 do
	  { Pr=Etap1(0);
		if((Pr==0)&&(Uslovie3( )==0)) Etap3( );
	  }
	 while (Pr!=1);
     L=Zel_f( );
     if (New( )==0) ij=-ij;
     Print_res( ij, out);
   }
   while (New( )!=0);
   fclose( out);
 }
