Preparing NOJ

0 or 1

2000ms 32768K

Description:

Given a n*n matrix Cij (1<=i,j<=n),We want to find a n*n matrix Xij (1<=i,j<=n),which is 0 or 1.

Besides,Xij meets the following conditions:

1.X12+X13+...X1n=1
2.X1n+X2n+...Xn-1n=1
3.for each i (1<i<n), satisfies ∑Xki (1<=k<=n)=∑Xij (1<=j<=n).

For example, if n=4,we can get the following equality:

X12+X13+X14=1
X14+X24+X34=1
X12+X22+X32+X42=X21+X22+X23+X24
X13+X23+X33+X43=X31+X32+X33+X34

Now ,we want to know the minimum of ∑Cij*Xij(1<=i,j<=n) you can get.
Hint

For sample, X12=X24=1,all other Xij is 0.

Input:

The input consists of multiple test cases (less than 35 case).
For each test case ,the first line contains one integer n (1<n<=300).
The next n lines, for each lines, each of which contains n integers, illustrating the matrix C, The j-th integer on i-th line is Cij(0<=Cij<=100000).

Output:

For each case, output the minimum of ∑Cij*Xij you can get.

Sample Input:

4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2

Sample Output:

3

Info

HDU

Provider HDU

Origin 2012 Multi-University Training Contest 8

Code HDU4370

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 08/17/2021 11:55:07

Related

Nothing Yet