/*                    Linear Assignment Problem
 *
 * Given a set of n agents and n tasks, assign tasks to agent such that
 * every agent has a unique task --- and, of course, every task has
 * someone performing it.  Find the optimal such assignment --- for our
 * purposes here, the one with the largest total benefit.
 *
 * There is a global matrix benefit[][] generated once the size is
 * known.  Also at the global level is a vector to receive the solution
 * and a variable to hold the value of the solution --- this is updated
 * as the program discovers permutations with a better value than the
 * presently stored permutation.
 *
 * The initial solution is generated as one of the two trivial solutions
 * --- either the diagonal solution (0, 1, 2, ...) or the antidiagonal
 * solution (...,2, 1, 0), whichever has the higher value --- as the sum
 * over k of benefit[k][solution[k]].  As a known solution, this
 * provides a lower limit when considering potential permutations.
 *
 * One can also quickly obtain an upper limit on a partial permutation.
 * While we are positioning values as [index], the known value for the
 * permutation will be the sum up to index of benefit[k][solution[k]].
 * Rows from [index+1] to [size-1] have not been assigned yet, and
 * correspondingly columns from perm[index+1] to perm[size-1] have not
 * been assigned.  One can obtain the column maximum value for each of
 * those columns and add them together.  The complete permutation cannot
 * possibly have a value greater than the total of its fixed part and
 * these column maxima, though it well might have one less.  If this
 * number is less than the already-known solution (lowerLimit), one can
 * immediately prune the decision tree --- discard this partial solution.
 *
 * Branch-and-Bound solution, using a "best-fit-first" rule for expanding
 * states.  As a maximization problem, it has been verified by experiment
 * that the priority queue should be driven by the present fixed value of
 * the permutation, not the upper-limit value discussed above.
 *
 * Language:  Java, version 5 or later (Scanner, printf)
 *
 * Author:  Timothy Rolfe
 */
import java.util.*;     // Scanner, PriorityQueue, . . .
import java.io.File;
public class AssignBandB
{
   // benefit matrix, which we're trying to maximize
   static int[][] benefit;
   static int[] solution;
   static int lowerLimit;
   static int size;
   static boolean TRACE = false;

   static class MyState implements Comparable
   {
      int[] vector;
      int   idx;
      int   score;
      int   myMax;

      MyState (int[] vector, int size, int idx, int score, int myMax)
      {
         this.vector = new int[size];
         System.arraycopy(vector, 0, this.vector, 0, size);
         this.idx   = idx;
         this.score = score;
         this.myMax = myMax;
      }

      // Reversed to get a max-priority-queue
      public int compareTo(Object o)
      {
         MyState rt = (MyState)o;
         int     diff = rt.idx - this.idx;
         if (diff != 0) return diff;
         else           return rt.score - this.score;
      }

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

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

   static void initialize(Scanner fptr)
   {
      int row, col, k,
          sum1 = 0, sum2 = 0;

      size = fptr.nextInt();
      benefit  = new int[size][size];
      solution = new int[size];

      for (row = 0 , k = size; row < size; row++)
      {  solution[row] = row;
         for (col = 0; col < size; col++)
            benefit[row][col] = fptr.nextInt();
         sum1 += benefit[row][row];
         sum2 += benefit[row][--k];     // Note predecrement of k
      }
      if (sum1 >= sum2)
         lowerLimit = sum1;
      else
      {  lowerLimit = sum2;
         col = size;
         for (row = 0; row < size; row++)
            solution[row] = --col;  // Antidiagonal
      }
   }

   static void displayCost()
   {
      int row, col;

      System.out.printf("Size %d\n", size);
      for (row = 0; row < size; row++)
      {  for (col = 0; col < size; col++)
            System.out.printf("%4d", benefit[row][col]);
         System.out.println();
      }
      System.out.printf("Lower bound: %d\nVector: ", lowerLimit);
      for (row = 0; row < size; row++)
         System.out.printf("%3d", solution[row]);
      System.out.println('\n');
   }

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

   static 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;
   }

   // Working from the global variables, obtain a maximal-benefit solution.
   // The initialize method has already computing the initial upper-limit
   // as the diagonal or antidiagonal permutation
   static void explore()
   {
      Queue<MyState> pq = new PriorityQueue<MyState>(128);

      pq.add( new MyState(solution, size, 0, 0, colMaxSum(0, solution)) );
      while (!pq.isEmpty())
      {
         MyState  eNode = pq.remove();
         int    score = eNode.score,
                myMax = eNode.myMax,
                idx   = eNode.idx;
         int[]  work  = eNode.vector;
         int    j, k;

         if (TRACE) System.out.printf("Expanding %s\n", eNode);
         if (myMax <= lowerLimit)
         {  if (TRACE) System.out.printf("Lower limit %d, so discard\n",
                lowerLimit);
            continue;      // I.e., discard
         }
         // Permute available scores through [idx]
         for ( j = idx; j < size; j++ )
         {  int workScore = score;
            MyState addendum;

            swap (work, idx, j);
            workScore += benefit[idx][work[idx]];
            // Compute the column maxima to the right of idx
            myMax = workScore + colMaxSum(idx+1, work);
            // Selecting [size-2] also fixes [size-1] ---
            // a permutation has been completed.
            if ( idx == size-2 )
            {
               if (myMax > lowerLimit)
               {
                  System.arraycopy(work, 0, solution, 0, size);
                  if (TRACE) System.out.printf("Accept, score > %d\n",
                                               lowerLimit);
                  lowerLimit = myMax;
               }
               else if (TRACE) System.out.printf("Reject, score <= %d\n",
                                                 lowerLimit);
            }
            else
            {
               addendum = new MyState(work, size, idx+1, workScore, myMax);
               if (myMax > lowerLimit)
               {
                   pq.add(addendum);
                   if (TRACE)
                      System.out.printf("\tMove forward with %s\n", addendum);
                }
               else if (TRACE)
                  System.out.printf("\tLower bound %d, so reject %s\n",
                     lowerLimit, addendum);
            }
         }
         // No need to regenerate the vector ---
         // the work vector is deleted along with eNode
      }
   }

   static void displaySolution()
   {
      int idx;

      System.out.printf("Branch-and-Bound sequential (%d): %d\n",
                        size, lowerLimit);
      for (idx = 0; idx < size; idx++)
         System.out.printf ("%3d", solution[idx]);
      System.out.println();
   }

   public static void main(String[] args) throws Exception
   {
      String  filename = args.length < 1 ? "A5" : args[0];
      Scanner fptr = new Scanner(new File(filename));
      long start, elapsed;

      System.out.printf("Reading from %s\n", filename);

      initialize(fptr);
      //displayCost();
      start = System.nanoTime();
      explore();
      elapsed = System.nanoTime() - start;
      displaySolution();
      System.out.printf("Time:  %3.3f seconds\n", 1E-09*elapsed);
   }
}