/********************************************************************
 ********************************************************************
 **
 ** libhungarian by Cyrill Stachniss, 2004
 **
 **
 ** Solving the Minimum Assignment Problem using the 
 ** Hungarian Method.
 **
 ** ** This file may be freely copied and distributed! **
 **
 ** Parts of the used code was originally provided by the 
 ** "Stanford GraphGase", but I made changes to this code.
 ** As asked by  the copyright node of the "Stanford GraphGase", 
 ** I hereby proclaim that this file are *NOT* part of the
 ** "Stanford GraphGase" distrubition!
 **
 ** This file is distributed in the hope that it will be useful,
 ** but WITHOUT ANY WARRANTY; without even the implied 
 ** warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 ** PURPOSE.  
 **
 ********************************************************************
 ********************************************************************/


#include <stdio.h>
#include <stdlib.h>
#include "hungarian.h"
#include "hungarian.c"

int main(int argc, char *argv[]) {

  hungarian_problem_t p;
  FILE *fp1, *fp2, *fp3;
  int *a, *c, *ca, *b, *ba, *d, *da, i, j, k, l, n, n2, n3, n4, le, r,s,matrix_size;
  int **C, **Ca;
  //int a[16] = {105, 105, 105, 105, 90, 90 ,90 ,90, 105, 105, 105, 105, 90, 90 ,90 ,90};
  //int a[16] = {0};
  fp1 = fopen(argv[1], "r");
  fp2 = fopen(argv[2], "w");
  fp3 = fopen("compara.out", "w");

  fscanf(fp1, "%d", &n);

  n2 = n*n;
  n3 = n2*n;
  n4 = n3*n;

  a = (int *)malloc(n2*sizeof(int));
  b = (int *)malloc(n2*sizeof(int));
  ba = (int *)malloc(n2*sizeof(int));
  c = (int *)malloc(n2*sizeof(int));
  ca = (int *)malloc(n2*sizeof(int));
  d = (int *)malloc(n4*sizeof(int));
  da = (int *)malloc(n4*sizeof(int));

  C = (int **)malloc(n*sizeof(int*));
  for(i=0; i<n; i++) C[i] = (int *)malloc(n*sizeof(int)); 

  Ca = (int **)malloc(n*sizeof(int*));
  for(i=0; i<n; i++) Ca[i] = (int *)malloc(n*sizeof(int)); 
  

  for(i=0; i<n; i++){
   for(j=0; j<n; j++){
     fscanf(fp1, "%d", &le);
     b[i*n+j] = le;
   }
  }

  for(i=0; i<n; i++){
   for(j=0; j<n; j++){
     fscanf(fp1, "%d", &le);
     c[i*n+j] = le;
   }
  }

  for(k=0; k<n; k++){
   for(i=0; i<n; i++){
      for(l=0; l<n; l++){
       for(j=0; j<n; j++){
	//fscanf(fp1, "%d", &le);
	d[k*n3+i*n2+l*n+j] = b[k*n+l]*c[i*n+j];
	da[k*n3+l*n2+i*n+j] = b[k*n+l]*c[i*n+j];
       }
      }
   }
  }

for(k=0; k<n; k++){
   for(i=0; i<n; i++){	
       for(l=0; l<n; l++){
        for(j=0; j<n; j++){
         if(k<l && i!=j){
	  d[k*n3+i*n2+l*n+j] += d[l*n3+j*n2+k*n+i];
	  d[l*n3+j*n2+k*n+i] = 0;
         }
        }
       }
   }
}
/*
  for(k=0; k<n; k++){
   for(i=0; i<n; i++){
      for(l=0; l<n; l++){
       for(j=0; j<n; j++){
	printf(" %d ", d[k*n3+i*n2+l*n+j]);
       }
	printf("\n");
      }
     printf("\n\n");	
   }
  }
*/

  for(k=0; k<n; k++){
   for(i=0; i<n; i++){


       for(l=0; l<n; l++){
        for(j=0; j<n; j++){
         if(k>l && i!=j){
	  d[k*n3+i*n2+l*n+j] += d[l*n3+j*n2+k*n+i];
	  d[l*n3+j*n2+k*n+i] = 0;
         }
        }
       }


       // preenchendo matriz C
       r = s = 0;
       for(l=0; l<n; l++){
        for(j=0; j<n; j++){
         if(k!=l && i!=j) {
			C[r][s] = d[k*n3+i*n2+l*n+j];
                        s++;
                      }
	}
        if (k != l) 
        {
           r++;
           s = 0;
        }
	printf("\n");
       }

       matrix_size = hungarian_init(&p, C, n - 1, n - 1, HUNGARIAN_MODE_MINIMIZE_COST) ;
  //     fprintf(stderr, "original cost-matrix:");
 //      hungarian_print_costmatrix(&p);
       hungarian_solve(&p);
   //    fprintf(stderr, "modified cost-matrix:");
   //    hungarian_print_costmatrix(&p);
       // preenchendo matriz a
       a[k*n+i] += hungarian_result(&p, C);

       // atualizando matriz d
       for(l=0; l<(n-1); l++){
        for(j=0; j<(n-1); j++){
           C[l][j] = hungarian_getcij(&p,l,j);
        }
       }

       r = s = 0;
       for(l=0; l<n; l++){
        for(j=0; j<n; j++){
         if(k!=l && i!=j)
         {
            d[k*n3+i*n2+l*n+j] = C[r][s];
            s++;
         }
	}
        if (k != l) 
        {
          r++;
          s = 0;
        }
       }
	
   }
   // eh aqui
  }

  for(i=0; i<n; i++){
   for(j=0; j<n; j++){
     printf(" %d ", a[i*n+j]);
   }
   printf("\n");
  }

for(k=0; k<n; k++){
   for(i=0; i<n; i++){	
       for(l=0; l<n; l++){
        for(j=0; j<n; j++){
         if(k<l && i!=j){
	  d[k*n3+i*n2+l*n+j] += d[l*n3+j*n2+k*n+i];
	  d[l*n3+j*n2+k*n+i] = 0;
         }
        }
       }
   }
}


// saida de dados

fprintf(fp2, "%d \n", n);
fprintf(fp2, "\n");

  for(i=0; i<n; i++){
   for(j=0; j<n; j++){
     fprintf(fp2, " %d ", a[i*n+j]);
   }
   fprintf(fp2, "\n");
  }
   fprintf(fp2, "\n");
/*
  for(i=0; i<n; i++){
   for(j=0; j<n; j++){
     fprintf(fp2, " %d ", b[i*n+j]);
   }
   fprintf(fp2, "\n");
  }
   fprintf(fp2, "\n");

  for(i=0; i<n; i++){
   for(j=0; j<n; j++){
     fprintf(fp2, " %d ", c[i*n+j]);
   }
   fprintf(fp2, "\n");
  }
   fprintf(fp2, "\n");

*/
  for(k=0; k<n; k++){
   for(i=0; i<n; i++){
      //fprintf(fp2,"%d %d\n\n",k,l);
      for(l=0; l<n; l++){
       for(j=0; j<n; j++){
	fprintf(fp2," %d ", d[k*n3+i*n2+l*n+j]);
         
       }
	fprintf(fp2, "\n");	
      }
fprintf(fp2, "\n");
fprintf(fp2, "\n");
   }
  }
/*
  for(k=0; k<n; k++){
   for(l=0; l<n; l++){
      fprintf(fp3,"%d %d\n\n",k,l);
      for(i=0; i<n; i++){
       for(j=0; j<n; j++){
	fprintf(fp3," %d ", da[k*n3+l*n2+i*n+j]);
         
       }
	fprintf(fp3, "\n");	
      }
fprintf(fp3, "\n");
fprintf(fp3, "\n");
   }
  }

*/
  hungarian_free(&p);


  return 0;
}

