#!/usr/bin/perl -w

open IN, "<".$ARGV[0] or die "Cannot open $1";
while (<IN>){
    $linea++;
    chomp;
    if ($linea ==1){
	if (/MAX/ || /max/ || /Max/){
	    $tipo = 1;
	}else { $tipo = 0 ; }
    }else{
	@lin = split / / ;
	$num=0;
	for $i (@lin){
	    $num++;
	    $costes[$linea-1][$num] = $i;
	}
	$N = $num;
    }
}
close IN;
if ($N != $linea-1) { die "Not a square matrix"; }
print "$N\n";
for $i (1..$N) {
    for $j (1..$N) {
	print "$costes[$i][$j] ";
    }
    print "\n";
}

for $i (1..$N){
    for $j (1..$N){
	if ($tipo==1){
	    $C[$i][$j]=-$costes[$i][$j];
	}else{
	    $C[$i][$j]=$costes[$i][$j];
	}
    }
}



#      SUBROUTINE JOVOFD(N,C,X,Y,U,V,Z)
#      INTEGER C(100,100),X(100),Y(100),U(100),V(100)
#      INTEGER H,Z,L0,V0,VJ,DJ,UP,LOW
#      INTEGER LAB(100),D(100),FREE(100),COL(100)
# C
# C THIS SUBROUTINE SOLVES THE FULL DENSITY LINEAR ASSIGNMENT PROBLEM
# C ACCORDING TO 
# C
# C   "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear   
# C    Assignment Problems," Computing 38, 325-340, 1987
# C   
# C   by
# C   
# C   R. Jonker and A. Volgenant, University of Amsterdam.
# C
# C INPUT PARAMETERS :
# C N = NUMBER OF ROWS AND COLUMNS
# C # C = WEIGHT MATRIX
# C
# C OUTPUT PARAMETERS
# C X = COL ASSIGNED TO ROW
# C Y = ROW ASSIGNED TO COL
# C U = DUAL ROW VARIABLE
# C V = DUAL COLUMN VARIABLE
# C Z = VALUE OF OPTIMAL SOLUTION
# C
# C INITIALIZATION
      for $I (1..$N){
        $X[$I]=0;
z10:  }
      for $J0 (1..$N){
        $J=$N-$J0+1;
        $VJ=$C[$J][1];
        $I0=1;
        for $I (2..$N){
          if ($C[$J][$I]<$VJ) {
            $VJ=$C[$J][$I];
            $I0=$I;
          }
z15:    }
        $V[$J]=$VJ;
        $COL[$J]=$J;
        if ($X[$I0]==0) {
          $X[$I0]=$J;
          $Y[$J]=$I0;
        }else{
          $X[$I0]=-abs($X[$I0]);
          $Y[$J]=0;
        }
z20:  }
      $L=0;
      for $I (1..$N){
        if ($X[$I]==0) {
          $L++;
          $FREE[$L]=$I;
          next;  # goto 40;
        }
        if ($X[$I]<0) {
          $X[$I]=-$X[$I];
        }else{
          $J1=$X[$I];
          $MIN=1.0E14;
          for $J (1..$N){
            next if ($J==$J1);  # goto 31
            if ($C[$J][$I]-$V[$J]<$MIN){ $MIN=$C[$J][$I]-$V[$J]; }
z31:      }
          $V[$J1]=$V[$J1]-$MIN;
        }
z40: }

# C IMPROVE THE INITIAL SOLUTION
      $CNT=0;
      if ($L==0) { goto z1000; }
z41:  $L0=$L;
      $K=1;
      $L=0;
z50:  $I=$FREE[$K];
      $K++;
      $V0=$C[1][$I]-$V[1];
      $J0=1;
      $VJ=1.0E14;
      for $J (2..$N){
        $H=$C[$J][$I]-$V[$J];
	  if ($H<$VJ) {
	      if ($H>=$V0) {
		  $VJ=$H;
		  $J1=$J;
	      }else{
		  $VJ=$V0;
		  $V0=$H;
		  $J1=$J0;
		  $J0=$J;
	      }
	  }
z42:  }
      $I0=$Y[$J0];
      if ($V0<$VJ) {
        $V[$J0]=$V[$J0]-$VJ+$V0;
      }else{
        if ($I0==0){ goto z43; }
        $J0=$J1;
        $I0=$Y[$J1];
      }
      if ($I0==0){ goto z43; }
      if ($V0<$VJ) {
        $K--;
        $FREE[$K]=$I0;
      }else{
        $L++;
        $FREE[$L]=$I0;
      }
z43:  $X[$I]=$J0;
      $Y[$J0]=$I;
      if ($K<=$L0) { goto z50; }
      $CNT++;
      if (($L>0)&&($CNT<2)) { goto z41; }

# C AUGMENTATION PART
      $L0=$L;
      for $L (1..$L0) { 
        $I0=$FREE[$L];
        for $J (1..$N){
          $D[$J]=$C[$J][$I0]-$V[$J];
          $LAB[$J]=$I0;
z51:    }
        $UP=1;
        $LOW=1;
z60:    $LAST=$LOW-1;
        $MIN=$D[$COL[$UP]];
        $UP++;
        for $K ($UP..$N){
          $J=$COL[$K];
          $DJ=$D[$J];
          if ($DJ<=$MIN) {
            if ($DJ<$MIN) {
              $MIN=$DJ;
              $UP=$LOW;
            }
            $COL[$K]=$COL[$UP];
            $COL[$UP]=$J;
            $UP++;
        }
z52:   }
       for $H ($LOW..$UP-1){
          $J=$COL[$H];
          if ($Y[$J]==0){ goto z70; }
z53:   }
z55:   $J0=$COL[$LOW];
        $LOW++;
        $I=$Y[$J0];
        $H=$C[$J0][$I]-$V[$J0]-$MIN;
        for $K ($UP..$N){
          $J=$COL[$K];
          $VJ=$C[$J][$I]-$V[$J]-$H;
          if ($VJ<$D[$J]) {
            $D[$J]=$VJ;
            $LAB[$J]=$I;
            if ($VJ==$MIN) {
              if ($Y[$J]==0) { goto z70; }
              $COL[$K]=$COL[$UP];
              $COL[$UP]=$J;
              $UP++;
            }
          }
z62:   }
        if ($LOW==$UP){ goto z60; }
        goto z55;
z70:   for $K (1..$LAST) { 
          $J0=$COL[$K];
          $V[$J0]=$V[$J0]+$D[$J0]-$MIN;
z71:    }
z80:   $I=$LAB[$J];
        $Y[$J]=$I;
        $K=$J;
        $J=$X[$I];
        $X[$I]=$K;
        if ($I0!=$I){ goto z80; }
z90:  }
      $Z=0;
      for $I (1..$N){ 
        $U[$I]=$C[$X[$I]][$I]-$V[$X[$I]];
        $Z+=$C[$X[$I]][$I];
z100: }
        &output();
z1000:  exit;


sub output {
#    for $i (1..$N){
#	for $j (1..$N){
#	    print "$C[$i][$j] ";
#	}
#	print "\n";
#    }
    print "\nRows assigned to columns:\n@X\nValue of objective function: $Z\n";
}

    
__END__