Write a program to permute the columns of a square matrix so as to minimize the sum of elements on the main diagonal.

If we number the columns in this matrix from 0 through 4 and then rearrange them so that they appear in the order8 16 15 91 64 83 42 93 75 27 76 95 75 81 50 20 42 96 90 24 38 28 2 15 81

then we get the matrix2 1 4 0 3

The sum of the elements on the main diagonal of this matrix is15 16 64 8 91 93 42 27 83 75 75 95 50 76 81 96 42 24 20 90 2 28 81 38 15

and no other permutation of the columns can yield a lower sum.15 + 42 + 50 + 20 + 15 = 142

This problem is known as the *assignment problem*, and it arises
in a great many industrial applications. For example, the columns
might represent jobs and the rows might represent workers, with
the matrix entry representing the number of hours it takes the
corresponding worker to complete the job. The solution to the
assignment problem tells us how to assign the workers to the jobs so
as to minimize the total number of hours worked. In the example above,
if we also label the rows from 0 to 4, then the given solution says
that we should assign job 2 to worker 0, job 1 to worker 1, job 4 to worker
2, job 0 to worker 3, and job 3 to worker 4 to get a total minimum of
142 hours worked.

**Input and Output format.**
Assume that the matrix is on standard input: the dimension N followed
by N lines with N integers per line.
You may assume that the entries are all between 0 and 999999.
Print the permutation and the total cost. For N less than 25, also print
the permuted output matrix.

**Reduction.**
Your assignment is to solve this problem by reducing it to the mincost
maxflow problem. You may use the code
`graph.h`,
`edge.c`, and
`graph.c`,
which comprise an implementation of the cycle-canceling algorithm from
the book (Program 22.8). The implementation uses the Bellman-Ford algorithm
to find negative cycles (Exercise 21.134).
*Do not modify this code at all*: just write a client program that
uses it. Following the vague description on page 462, your reduction
will be like the one in Program 22.6 on page 421, but your code will
be different because you are starting with a matrix, not a network,
and because you are reducing to a flow network with costs.

**Analysis.**
Once you get your program debugged and working for small N, run it for
larger values of N, stopping when your runtime exceeds 1 minute. You
can use the program
`generate.c`
to generate random matrices. Develop a
formula that you can use to predict the running time of the program,
as a function of N. Give both the exponent and constant in your formula.

**Extra Credit.**
The assignment is an exercise in reduction and does not reflect the
way assignment problems are solved in industrial applications, for
two primary reasons. First, in real applications, the matrices involved are
sparse: for example, each worker is likely to be qualified
to do a few jobs, but not every job. Second, mincost-maxflow problems
are so widely applicable that fast optimized solvers are widely available.
Since the solvers are designed for sparse graphs, they use a sparse input
format, such as a list of edges.
Even so, we can go ahead and apply an industrial strength solver designed
for sparse inputs to our dense input instances.

For extra credit, use the min cost flow solver. developed by Andrew Goldberg. Goldberg's implementation uses a sophisticated cost-scaling successive approximation algorithm for the min cost flow problem. Goldberg's algorithm uses the DIMACS file format, so you will need to translate our input format to DIMACS form. Run experiments and develop a formula that you can use to predict the running time of this solution, as a function of N.