/* Linear Assignment Problem --- moving towards parallel solution of the
 * Branch-and-Bound implementation.
 *
 * Separate the priority queue portion (which will be implemented in
 * the master process) from the state expansion portion (which will be
 * in the slave processes).  For this implementation, however, the
 * priority queue portion simply calls the state expansion portion in a
 * strictly sequential version.  In the parallel version, this function
 * call will become communication with the slave processes --- receiving
 * messages containing 0 or more expanded states and sending a single
 * state to be expanded by the slave --- or sending a termination message.
 *
 * Language:  Java, version 5 or later (Scanner, printf), although the
 * parallel version (under PVM and/or MPI) will be in C++, simplifying
 * the use of MyState objects.
 *
 * Author:  Timothy Rolfe
 */
import java.util.*;
import java.io.*;

public class Sequential
{
   // Diagonal permutation sets solution, maxValue AND lowerLimit
   int solution[], lowerLimit;
   int size, benefit[][];
   boolean DEBUG = false;

   class MyState implements Comparable
   {
      int []vector;
      int   index;
      int   value;
      int   myMax;

      MyState (int []vector, int index, int value, int myMax)
      {
         this.vector = (int[]) vector.clone();
         this.index  = index;
         this.value  = value;
         this.myMax  = myMax;
      }

      // Note:  inverted comparison for max-priority-queue behavior
      public int compareTo(Object o)
      {  return ((MyState)o).value - this.value;  }

      public String toString()
      {  StringBuilder msg = new StringBuilder();

         msg.append(String.format("[%d] value %d, max %d:  ",
            index, value, myMax) );
         for (int k = 0; k < size; k++)
            msg.append(String.format("%3d", vector[k]) );
         return msg.toString();
      }
   } // end class MyState

   void swap(int[] x, int p, int q)
   {  int temp = x[p]; x[p] = x[q];  x[q] = temp;  }

   int colMaxSum(int start, int []work)
   {  int sum = 0;
      for (int k = start; k < size; k++)
      {
         int row, col = work[k],
             columnMaximum = benefit[start][col];
         for (row = start+1; row < size; row++)
            if (columnMaximum < benefit[row][col])
                columnMaximum = benefit[row][col];
         sum += columnMaximum;
      }
      return sum;
   }

   // In entry, inOut[0] contains the state to be expanded
   // On exit, inOut contains the states generated, and the
   // number generated is returned as the function value;
   public int expand(MyState inOut[])
   {
      int vector[] = inOut[0].vector;
      int index    = inOut[0].index,
          value    = inOut[0].value;
      int n        = 0, // Number of states put INTO inOut
          newValue,     // Adding in benefit[index][vector[index]]
          myMax,        // Upper limit from column maxima
          k;            // Loop variable

      if (DEBUG)
      {  StringBuilder msg = new StringBuilder();

         msg.append(String.format("Expending [%d] bound %d: ",
                    index, inOut[0].myMax));
         for (k = 0; k < size; k++)
            msg.append(String.format("%3d", vector[k]));
         System.out.println(msg.toString());
      }
      for (k = index; k < size; k++)
      {
         swap (vector, index, k);
         newValue = value + benefit[index][vector[index]];
         myMax = newValue + colMaxSum(index+1, vector);
         if (myMax < lowerLimit)
         {
            if (DEBUG)
               System.out.printf("Discard %d < %d\n",
                  myMax, lowerLimit);
            continue;
         }
         inOut[n++] = new MyState (vector, index+1, newValue, myMax);
         if (DEBUG)
            System.out.printf("Adding %s\n", inOut[n-1]);
      }
      return n;
   }

   static void displaySolution(int []solution, int lowerLimit)
   {
      int idx;

      System.out.printf("Alternative BandB sequential (%d): %d\n",
                        solution.length, lowerLimit);
      for (idx = 0; idx < solution.length; idx++)
         System.out.printf ("%3d", solution[idx]);
      System.out.println();
   }

   public static void main (String[] args)throws Exception
   {  new Sequential().process(args);  }

   void process(String[] args) throws Exception
   {
      String filename = args.length == 0 ? "A5" : args[0];
      Scanner input = new Scanner( new File(filename) );
      int row, col, j, k, work[];
      int antiSum = 0;
      long start, elapsed;

      size = input.nextInt();
      solution = new int[size];
      benefit = new int[size][size];
      for (row = lowerLimit = 0, k = size; row < size; row++)
      {  solution[row] = row;
         for (col = 0; col < size; col++)
            benefit[row][col] = input.nextInt();
         lowerLimit += benefit[row][row];
         antiSum  += benefit[row][--k];
      }
      if (antiSum > lowerLimit)
      {  lowerLimit = antiSum;
         for (j = 0, k = size; j < size; j++)
            solution[j] = --k;
      }
      work = (int[]) solution.clone();
      start = System.nanoTime();
      findMax(work);
      elapsed = System.nanoTime() - start;
      displaySolution(solution, lowerLimit);
      System.out.printf("Time:  %3.3f seconds\n", 1E-09*elapsed);
   }

   void findMax(int[] perm)
   {  MyState[] inOut = new MyState[size]; // Vector of states from expand
      int nEntries,                        // Actual entries in the vector
          entry;                           // Loop variable
      Queue<MyState> work = new PriorityQueue<MyState>();

      work.add ( new MyState ( perm, 0, 0, colMaxSum(0, perm) ) );
      while ( ! work.isEmpty() )
      {
         inOut[0] = work.remove();
         if (inOut[0].myMax <= lowerLimit)
         {  if (DEBUG)
               System.out.println("Discard unprocessed " + inOut[0]);
            continue;
         }
         nEntries = expand(inOut);
         if (nEntries == 0)
            continue;
         if (inOut[0].index < size-1)
         {  for (entry = 0; entry < nEntries; entry++)
               if (inOut[entry].myMax > lowerLimit)
                  work.add(inOut[entry]);
         }
         else
         {  for (entry = 0; entry < nEntries; entry++)
               if (inOut[entry].myMax > lowerLimit)
                  update(inOut[entry]);
         }
      }
   }

   // NOTE:  This is called when better.index == size-2, so that
   // better.myMax is actually the full value of the state
   synchronized void update(MyState better)
   {
      if (DEBUG)
         System.out.printf("Replacing %d with %d:  %s\n",
            lowerLimit, better.myMax, better);
      lowerLimit = better.myMax;
      System.arraycopy(better.vector, 0, solution, 0, size);
   }
}