Elvirius Sth. Recorded

#include <stdio.h>
#define MAX_SIZE 50

typedef struct matrix
{
 int cost[MAX_SIZE][MAX_SIZE];
 int ori_cost[MAX_SIZE][MAX_SIZE];
 int height;

 int zeros;
 int row_zeros[MAX_SIZE];
 int col_zeros[MAX_SIZE];

 int row_lined[MAX_SIZE];
 int col_lined[MAX_SIZE];
 int result_idx;
 int result[MAX_SIZE][2];
} matrix;

int temp[MAX_SIZE][MAX_SIZE] = {0};

matrix matrix_input();
void calc_zeros(matrix &mt);
void select_zeros(matrix &mt);
void output_result(matrix &mt);
void re_calculation(matrix &mt);
void dual_optimal(matrix &mt);

void debug_mt(matrix &mt) {
 int i = 0, j = 0;
 printf("\nMatrix Data:\n");
 for (i = 0; i < mt.height; i ++) {
  for (j = 0; j < mt.height; j ++)
   printf("%4d", mt.cost[i][j]);
  printf("\n");
 }
}

void select_zeros(matrix &mt)
{
 int i = 0, j = 0;
 int min_zeros = mt.height, min_zeros_idx = mt.height, last_min_zeros = 0;
 int last_matrix_zeros = mt.zeros + 1;
 
 mt.result_idx = 0;
 
 while (last_matrix_zeros > mt.zeros) {
  last_matrix_zeros = mt.zeros;
  min_zeros = mt.height;  
  min_zeros_idx = mt.height; 
  for (i = 0; i < mt.height; i ++) {
   if (mt.row_lined[i] == 0 && mt.row_zeros[i] < min_zeros && mt.row_zeros[i] != 0) {
    min_zeros = mt.row_zeros[i];
    min_zeros_idx = i;
   }
  }
  last_min_zeros = min_zeros; 
  for (j = 0; j < mt.height; j ++) {
   if (mt.col_lined[j] == 0 && mt.col_zeros[j] < min_zeros && mt.col_zeros[j] != 0) {
    min_zeros = mt.col_zeros[j];
    min_zeros_idx = j;
   }
  }
  if (min_zeros != mt.height) { 
   if (last_min_zeros == min_zeros) { 
    for (j = 0; j < mt.height; j ++) {
     if (mt.col_lined[j] == 0 && mt.cost[min_zeros_idx][j] == 0)
      break;
    }
    if (j < mt.height) {
     mt.col_lined[j] = 1;
     mt.result[mt.result_idx][0] = min_zeros_idx;
     mt.result[mt.result_idx][1] = j;
     mt.col_zeros[j] --;
     mt.row_zeros[min_zeros_idx] --;
     mt.zeros --;
     mt.result_idx ++;
    }
   } else {
    for (i = 0; i < mt.height; i ++) {
     if (mt.row_lined[i] == 0 && mt.cost[i][min_zeros_idx] == 0)
      break;
    }
    if (i < mt.height) {
     mt.row_lined[i] = 1;
     mt.result[mt.result_idx][0] = i;
     mt.result[mt.result_idx][1] = min_zeros_idx;
     mt.col_zeros[min_zeros_idx] --;
     mt.row_zeros[i] --;
     mt.zeros --;
     mt.result_idx ++;
    }
   }
  }
 }

 if (mt.result_idx == mt.height) {
  //If any echos
  output_result(mt);
 } else {
  //If any echos
  re_calculation(mt);
 }
}

void re_calculation(matrix &mt) {
 int i = 0, j = 0, min_d = 65535;
 for (i = 0; i < mt.height; i ++) {
  if (mt.row_lined[i] != 0)
   continue;
  for (j = 0; j < mt.height; j ++) {
   if (mt.col_lined[j] != 0)
    continue;
   temp[i][j] = mt.cost[i][j];
   if (temp[i][j] > min_d)
    min_d = temp[i][j];
  }
 }
 printf("Prepare for data adjustment...");
 debug_mt(mt);
 for (i = 0; i < mt.height; i ++) {
  for (j = 0; j < mt.height; j ++) {
   if (temp[i][j] == 0 && mt.row_lined[i] == 1 && mt.col_lined[j] == 1) {
    temp[i][j] = mt.cost[i][j] + min_d;
    mt.cost[i][j] = temp[i][j];
   } else if (temp[i][j] == 1) {
    temp[i][j] -= min_d;
    mt.cost[i][j] = temp[i][j];
   }   
  }
 }
 printf("Data after adjustment:");
 debug_mt(mt);
 calc_zeros(mt);
 select_zeros(mt);
}

void output_result(matrix &mt) {
 int i = 0, total = 0;
 printf("\nComputed Result:\n");
 for (i = 0; i < mt.result_idx; i ++) {
  total += mt.ori_cost[mt.result[i][0]][mt.result[i][1]];
  printf("(%d, %d)[%d] -> ", mt.result[i][0], mt.result[i][1], mt.ori_cost[mt.result[i][0]][mt.result[i][1]]);
 }
 printf("The Optimized Result: %d", total);
}

matrix matrix_input()
{
 matrix mt;
 int workers = 0, jobs = 0, i = 0, j = 0;
 char w = 0;

 printf("Hungarian Method for Integer Programmin' (Minimal Optimization):\n");
 //Programmed by Sirius Ding. THX.
 printf("Input the number of work units ( should between 1 to %d):\n", MAX_SIZE);
 scanf("%d", &workers);
 while(workers < 1 || workers > MAX_SIZE) {
  printf("Valid input required, again, please:\n");
  scanf("%d", &workers);
 }
 printf("Input the number of work projects( should between 1 to %d):\n", MAX_SIZE);
 scanf("%d", &jobs);
 while(jobs < 1 || jobs > MAX_SIZE) {
  printf("Valid input required, again, please:\n");
  scanf("%d", &jobs);
 }
 printf("Please input a matrix with dimension: %d rows %d columns.\nUse `space` to separate elements in the same row, and `enter` to switch to next row:\n",workers,jobs);
 for(i = 0; i < workers; i ++) {
  for(j = 0; j < jobs; j ++) {
   scanf("%d", &mt.cost[i][j]);
   mt.ori_cost[i][j] = mt.cost[i][j];
  }
 }
 printf("Finished Matrix Input, Press Enter to continue.");
 scanf("%c", &w);

 if(jobs > workers) {
  for(i = workers; i < jobs; i ++) {
   for(j = 0; j < jobs; j ++) {
    mt.cost[i][j] = 0;
    mt.ori_cost[i][j] = 0;
   }
  }
 } else if(workers > jobs) {
  for(i = 0; i < workers; i ++) {
   for(j = jobs;j < workers; j ++) {
    mt.cost[i][j]=0;
    mt.ori_cost[i][j]=0;
   }
  }
 }
 mt.height = (workers > jobs) ? workers : jobs;
 return mt;
}

void calc_zeros(matrix &mt)
{
 int i = 0, j = 0, k = 0;
 for(i = 0; i < mt.height; i ++)
 {
  k = mt.cost[i][0];
  mt.row_zeros[i] = 0;
  mt.row_lined[i] = 0;
  mt.col_lined[i] = 0;
  if (k == 0) continue;
  for(j = 1; j < mt.height; j ++)
   if(mt.cost[i][j] < k)
    k = mt.cost[i][j];
  if (k == 0) continue;
  for(j = 0; j < mt.height; j ++)
   mt.cost[i][j] = mt.cost[i][j] - k;
 }
 for(j = 0; j < mt.height; j++)
 {
  k = mt.cost[0][j];
  mt.col_zeros[j] = 0;
  if (k == 0) continue;
  for(i = 1; i < mt.height; i ++)
   if(mt.cost[i][j] < k)
    k = mt.cost[i][j];
  if (k == 0) continue;
  for(i = 0; i < mt.height; i ++)
   mt.cost[i][j] = mt.cost[i][j] - k;
 }
 mt.zeros = 0;
 for (i = 0; i < mt.height; i ++) {
  for (j = 0; j < mt.height; j ++) {
   if (mt.cost[i][j] == 0) {
    mt.row_zeros[i] ++;
    mt.col_zeros[j] ++;
    mt.zeros ++;
   }
  }
 }
}

void dual_optimal(matrix &mt) {
 int i = 0, j = 0, k = 0, t = 0, row_min = 0;
 int u[MAX_SIZE] = {0}, v[MAX_SIZE] = {0};
 int u_idx_i = 0, u_idx_j = 0, dual_optimal = 0, coef = 0;
 for (i = 0; i < mt.result_idx; i ++) {
  u_idx_i = mt.result[i][0];
  u_idx_j = mt.result[i][1];
  t = mt.ori_cost[u_idx_i][u_idx_j];
  
  row_min = mt.ori_cost[u_idx_i][0];
  for (k = 0; k < mt.height; k ++) {
   if (mt.ori_cost[u_idx_i][k] < row_min)
    row_min = mt.ori_cost[u_idx_i][k];
  }
  for (j = 0; j <= t; j ++) {
   if (j <= row_min && t - j <= row_min) {
    u[u_idx_i] = j;
    v[u_idx_j] = t - j;
   }
  }
 }
 for (i = 0; i < mt.height; i ++)
  coef += mt.ori_cost[i][i] - u[i] - v[i];
 printf("\nDual Optimal listing:\n");
 for (i = 0; i < mt.height; i ++) {
  dual_optimal += u[i] + v[i];
  printf("u*(%d) = %3d, v*(%d) = %3d\n", i, u[i], i, v[i]);
 }
 printf("Dual Optimal %d \nAdjustment coef. is %d \n", dual_optimal, coef);
}

int main(int argc, char * argv[])
{
 matrix mt;
 mt = matrix_input();
 debug_mt(mt);
 calc_zeros(mt);
 debug_mt(mt);
 select_zeros(mt);
 dual_optimal(mt);
 return 0;
}