/********************************************************
*                 APPOINTMENT METHOD                    *
*                 ------------------                    *
*                                                       *
* LIST OF MAIN VARIABLES:                               *
*                                                       *
*  NP:         NUMBER OF JOBS                           *
*  C(NP,NP):   APPOINTMENT COST MATRIX                  *
*  MP(NP,NP):  JOB/APPLICANT MATRIX                     *
*  IF1:        FLAG=1 IF OPTIMAL APPOINTMENT IS FOUND   *
*  IZ:         FLAG TO MARK A ZERO                      *
*  XMIN:       MINIMUM VALUE                            *
*  XCASE:      APPOINTMENT OF A ZERO IN RELATION WITH   *
*              THE ZEROES' MINIMUM                      *
*  NZ:         NUMBER OF ZEROES                         *
*  ZI,ZJ:      COORDINATES OF CURRENT CASE              *
*  M,N:        COORDINATES OF A MARKED ZERO             *
*  A,B:        AUXILIARY VARIABLES TO CHANGE            *
*              APPOINTMENTS.                            *
* ----------------------------------------------------- *
* PROBLEM DESCRIPTION                                   *
* An employer receives four applicants for four avail-  *
* able jobs. They must give a mark from 1 to 100 to     *
* each job (1=very poor preference, 100=very good).     *
* See table below:                                      *
*                    J O B S                            *
*                 J1  J2  J3  J4                        *
*              A1 90  80  20  40                        *
*  APPLICANTS  A2 90  70  30  80                        *
*              A3 40  70  20  80                        *
*              A4 50  40  20  60                        *
* The employer's purpose is to appoint the four jobs so *
* as to maximize the applicants' satisfaction.          *
* ----------------------------------------------------- *
* SAMPLE RUN:                                           *
* (appoint four jobs with the following regrets matrix: *
*                    J O B S                            *
*                 J1  J2  J3  J4                        *
*              A1 10  20  80  60                        *
*  APPLICANTS  A2 10  30  70  20                        *
*              A3 60  30  80  20                        *
*              A4 50  60  80  40   )                    *
*                                                       *
* LINEAR PROGRAMMING                                    *
*                                                       *
* APPOINTMENT METHOD                                    *
*                                                       *
* NUMBER OF JOBS ? 4                                    *
*                                                       *
* INPUT APPOINTMENT COSTS/REGRETS OF APPLICANTS:        *
*                                                       *
* APPLICANT #1:                                         *
*    JOB #1 ? 10                                        *
*    JOB #2 ? 20                                        *
*    JOB #3 ? 80                                        *
*    JOB #4 ? 60                                        *
*                                                       *
* APPLICANT #2:                                         *
*    JOB #1 ? 10                                        *
*    JOB #2 ? 30                                        *
*    JOB #3 ? 70                                        *
*    JOB #4 ? 20                                        *
*                                                       *
* APPLICANT #3:                                         *
*    JOB #1 ? 60                                        *
*    JOB #2 ? 30                                        *
*    JOB #3 ? 80                                        *
*    JOB #4 ? 20                                        *
*                                                       *
* APPLICANT #4:                                         *
*    JOB #1 ? 50                                        *
*    JOB #2 ? 60                                        *
*    JOB #3 ? 80                                        *
*    JOB #4 ? 40                                        *
*                                                       *
* APPOINTMENTS:                                         *
*                                                       *
*       APPLICANT #1 => JOB #2                          *
*       APPLICANT #2 => JOB #1                          *
*       APPLICANT #3 => JOB #4                          *
*       APPLICANT #4 => JOB #3                          *
*                                                       *
* ----------------------------------------------------- *
* REFERENCE:                                            *
* Modèles pratiques de décision Tome 2, By Jean-Pierre  *
* Blanger, PSI Editions, France, 1982.                  *
*                                                       *
*               C++ Release 1.0 By J-P Moreau, Paris.   *
*                        (www.jpmoreau.fr)              *
********************************************************/
#include <stdio.h>
#include <math.h>

#define  NMAX  10

    double C[NMAX][NMAX];
    int MP[NMAX][NMAX];
    int IF1,IZ,M,N,NP,NZ,ZI,ZJ;
    double A,B,XCASE,XMIN;


void Data() {  //INPUT COST/APPOINT
  int I,J;
  printf("\n LINEAR PROGRAMMING\n\n");
  printf(" APPOINTMENT METHOD\n\n");
  printf(" NUMBER OF JOBS ? "); scanf("%d", &NP);
  printf("\n INPUT APPOINTMENT COSTS/REGRETS OF APPLICANTS:\n");
  for (I=1; I<=NP; I++) {
    printf("\n APPLICANT #%d:\n", I);
    for (J=1; J<=NP; J++) {
      printf("    JOB #%d ? ", J);
      scanf("%lf", &C[I][J]);
    }
  }
  printf("\n APPOINTMENTS:\n\n");
}

    void Zeroes();
    void Appoint();
    void Mark();
    void Sub_add();

void Sub_Main()  {  //HUNGARIAN ALGORITHM
e10:Zeroes();
    Appoint();
    Mark();
    Sub_add();
    Appoint();
    if (IF1 != NP) goto e10;
}

void Zeroes()  {
  int I,J;
  double R;
  IZ = 0; R = 0;
  for (I=1; I<=NP; I++) {
    XMIN = C[I][1];
    for (J=1; J<=NP; J++) {
 	  if (C[I][J] == 0) IZ = 1;
	  if (C[I][J] < XMIN) XMIN = C[I][J];
    }
    if (IZ == 1) {
      IZ = 0; goto e10;
    }
    for (J=1; J<=NP; J++)
	  C[I][J] -= XMIN;
e10:;}
  for (J=1; J<=NP; J++) {
    XMIN = C[1][J];
    for (I=1; I<=NP; I++) { 
      if (C[I][J] == 0) IZ = 1;
	  if (C[I][J] < XMIN) XMIN = C[I][J];
    }
    if (IZ == 1) {
	  IZ = 0; goto e20;
    }
    for (I=1; I<=NP; I++)
	  C[I][J] -= XMIN;
e20:;}
}

void Appoint() {
  int I,J,K;
  for (I=1; I<=NP; I++) {
    for (J=1; J<=NP; J++) {
	  MP[I][J] = 0; C[0][J] = 0;
    }
    C[I][0] = 0;
  }
  for (I=1; I<=NP; I++) {
    XCASE = 999999;
    for (J=1; J<=NP; J++) {
      if (C[I][J] != 0 || MP[I][J] != 0) goto e10;
	  NZ = 0;
      for (K=1; K<=NP; K++)
	    if (C[K][J] == 0) NZ++;
	  if (1.0*NZ < XCASE) {
	    XCASE = 1.0*NZ; ZI = I; ZJ = J;
	  }
e10:;}
     MP[ZI][ZJ] = 1;
     for (K=1; K<=NP; K++)
	   if (C[K][ZJ] == 0 && MP[K][ZJ] == 0)  MP[K][ZJ] = -1;
     for (K=1; K<=NP; K++)
	   if (C[ZI][K] == 0 && MP[ZI][K] == 0)  MP[ZI][K] = -1;
  }
  IF1 = 0;
  for (I=1; I<=NP; I++)
    for (J=1; J<=NP; J++)
      if (MP[I][J] == 1) IF1++;
}

void Mark() {
  int I,J;
e10: for (I=1; I<=NP; I++) {
       N = 0;
       for (J=1; J<=NP; J++)
	     if (MP[I][J] == 1)  N = 1;
	   if (N == 0 && C[I][0] == 0) {
	     C[I][0] = 1; M = 1;
       }
     }
     for (J=1; J<=NP; J++)
       for (I=1; I<=NP; I++)
		 if (MP[I][J] == -1 && C[I][0] == 1 && C[0][J] == 0) {
	       C[0][J] = 1; M = 1;
		 }
     for (I=1; I<=NP; I++)
       for (I=1; I<=NP; I++)
		 if (MP[I][J] == 1 && C[0][J] == 1 && C[I][0] == 0) {
	       C[I][0] = 1; M = 1;
		 }
	 if (M == 1) {
       M = 0; goto e10;
     }
}

void Sub_add() {
  int I,J;
  XMIN = 999999;
  for (I=1; I<=NP; I++)
    for (J=1; J<=NP; J++) {
      A = C[I][0]; B = C[0][J];
      if (A == 1 && B == 0 && C[I][J] < XMIN)  XMIN = C[I][J];
    }
  for (I=1; I<=NP; I++)
	for (J=1; J<=NP; J++) {
      A = C[I][0]; B = C[0][J];
      if (A == 1 && B == 0)  C[I][J] -= XMIN;
      if (A == 0 && B == 1)  C[I][J] += 2 * XMIN;
    }
}

void Results()  {
  int I,J;
  for (I=1; I<=NP; I++)
    for (J=1; J<=NP; J++) {
      if (MP[I][J] != 1) goto e10;
 	  printf("       APPLICANT #%d => JOB #%d\n", I, J);
e10:;}
  printf("\n");
}

void main() {

  Data();     // INPUT COST/APPOINT}
  Sub_Main(); // HUNGARIAN ALGORITHM
  Results();  // PRINT RESULTS

}

// END OF FILE APPOINT.CPP