P3236 [HNOI2014] Picture Frames

Xiao T (小 T) plans to place several paintings at home. He has bought $N$ paintings and $N$ frames. To show his taste, he wants to match paintings with frames so that the result is neither too plain nor too jarring. For the pairing of painting $i$ with frame $j$, Xiao T assigns a plainness value $A_{i, j}$ and an incompatibility value $B_{i, j}$. The overall disharmony of a complete matching is defined as the product of the sum of plainness values over all matched pairs and the sum of incompatibility values over all matched pairs. Specifically, let painting $i$ be matched with frame $p_i$; then the overall disharmony is $$\mathrm{disharmony}=\sum_{i=1}^{N}A_{i,p_i}\times \sum_{i=1}^{N}B_{i,p_i}.$$ Xiao T wants to know the minimum possible overall disharmony.

The first line contains a positive integer $T$, the number of test cases. For each test case: - The first line contains a positive integer $N$, the number of paintings and frames. - Lines $2$ through $N+1$ each contain $N$ non-negative integers; on line $i+1$, the $j$-th number is $A_{i, j}$. - Lines $N+2$ through $2N+1$ each contain $N$ non-negative integers; on line $i+N+1$, the $j$-th number is $B_{i, j}$.

Output $T$ lines, each containing one integer: the minimum overall disharmony.

If painting $1$ is matched with frame $3$, painting $2$ with frame $1$, and painting $3$ with frame $2$, then the overall disharmony is $30$. Constraints: For $100\%$ of the testdata, $N \leq 70$, $T \leq 3$, $A_{i, j} \leq 200$, $B_{i, j} \leq 200$. Translated by ChatGPT 5