Peter is a student of Professor Karn, who teaches networking. However, due to some private issue Karn dislike Peter and always treat him very bad.
In a rainy day of August Professor Karn summoned Peter and tell him:
" Hey, you know what? I want to design a network where the maximum flow between node 0 and node 1 is 13, the maximum flow between node 0 and node 2 is 17, the ..."
After around an hour of talking non-stop, Karn finally finished his description of the maximum flow between all 200 nodes of his desired network pairwisely. Just when Peter thought to himself finally it's over, Professor Karn continues to announce the bad news, (as always)
"You know what's better? YOU, have to find a way to build the network for me. Furthermore, you have to find a way to build the network with minimum cost. Using an edge of capacity C costs exactly C, and the total cost is simply the summation of all edges' cost."
Being always treated unfair, Peter thinks it's his good chance for revenge. He decides to play a little joke on Professor Karn, instead of telling him the minimum cost required to build such graph, he decides to tell him the MAXIMUM cost!!! HAHAHA, VERY FUNNY, PETER!!!
Anyway, help Peter get on Karn his time and I'm sure you'll be rewarded (by TA Karn :p).
P.S. all edges in the network are considered undirected!
The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing n (0 < n ≤ 200), followed by n lines with n integers each, giving the matrix T which is the maximum flow matrix between the nodes pairwisely.
* T[u][u] will always be 0.<br/>
* T[u][v] will always be positive and equal to T[v][u].<br/>
* T[i][j] ≤ 10000<br/>
T[u][v] is maximum flow between node u and v.
For each test case, output one line containing "Case #x:" followed by s - the maximum cost possible.
If there is no solution, that means Professor Karn is just picking on you, print "I'm sorry, Professor Karn".
For those who do not understand the... uh, story in the problem decription, here's a brief recap of what's to be done in this problem :p
In the problem a matrix M is given, which represents the maximum flow between all pairs of nodes in some particular graph G (unknown to you). This means that ASSUME you know G, then:
   M[i][j] = the maximum flow on G when node i is source and node j is sink.
Given this information, you are asked to find some possible graph G that would have such a maximum-flow matrix and output the sum of all edge's capacity in G, and in case there's multiple possibility of this value, choose a G that maximize this sum of capacity. On the other hand, if such G does not exist, say sorry to Karn.
Migrated from old NTUJ.
uva11603, modified: kelvin
| No. | Testdata Range | Score |
|---|