(Unlock problem I if any team solved this problem!)
In the Triangle Country, there are many roads connected some pair of cities. Actually, there is a road directly connected every pair of cities. Some of the roads were uni-directional, and others used to be bi-directional. But, the roads are too narrow, so eventually only one direction is allowed. The people in Triangle Country loves triangles. They want triangulation everywhere. So, they need you to decide the direction of all bi-directional roads such that the number of “Hilarious Inner Triangles” (HIT for short) is maximized. Where a HIT is a pair of three cities (a, b, c) and the three directional roads are from a to b, b to c, and from c to a.
First line contains an integer T(1<=T<=10) indicating the number of test cases.
For each test case, first line contains an integer n (1<=n<=100), indicating the number of cities. Next there are a n by n matrix fulfilled with markers 0, 1, or 2. For a number aij in i-th row and j-th column, if aij = 1, it means the road is directional from i to j. If aij = 2, it means the direction is undetermined.
For each test case, please output the maximum possible number of HITs.
1 3 0 1 2 0 0 2 2 2 0
1
Migrated from old NTUJ.
Shik and Tmt
| No. | Testdata Range | Score |
|---|