P17805 [ICPC 2019 Nanchang R] A Funny Bipartite Graph

Bob is really interested in bipartite graph, and he needs help for this problem: :::align{center}  ::: Bob has a bipartite graph which meets all the conditions below: - The left part has $n$ ($1\leq n\leq 18$) vertices, named $L_1, L_2, \cdots, L_n$. And the right part also has $n$ vertices, named $R_1, R_2, \cdots, R_n$. - $L_i$ **never** connects with $R_j$ when $i>j$ for all pairs of $(i,j)$ that $1\leq i,j\leq n$. - For each vertex on the left part $L_i$ ($1\leq i\leq n$), its degree $D_i$ is at most $3$ and at least $1$ ($1\leq D_i\leq 3$). Bob wants to select some edges from the graph such that the selected edges and their endpoints form a new graph. However, he should obey these rules: - Some pairs of vertices can't appear in the new graph together. You are given an $n\times n$ matrix $A$, $A_{i,j}$ is $1$ if and only if $L_i$ and $L_j$ can't appear in the new graph together. - Bob must ensure that the selected edges cover all the right vertices. In other words, every right vertex should appear in the new graph. - Every left vertex $L_i$ ($1\leq i\leq n$) has a magic number $M_i$ ($1\leq M_i\leq 100$). If $L_i$ appears in the new graph, its cost is ${M_i}^{d_i}$, where $d_i$ is the degree of $L_i$ in the new graph, otherwise its cost is zero. Now Bob wants to select edges satisfying the rules above with minimum total cost. Please write a program to help him find the minimum total cost, or determine it is impossible to get such a valid new graph.

There are several test cases in the input file. The first line contains one integer $T$ ($1\leq T\leq 10$) --- number of the test cases. For each case: The first line contains one integer $n$ ($1\leq n\leq 18$) --- number of the left vertices. The following $n$ lines are about the graph edges information with an $n\times n$ matrix $G$. The $i$-th line contains a 01-string $G_i$ and the $j$-th character $G_{i,j}$ is $1$ if and only if $L_i$ and $R_j$ are connected, otherwise $G_{i,j}$ is $0$. We guarantee that the degree of each left vertex $L_i$ is between $1$ and $3$. We also guarantee that $G_{i,j}$ is always $0$ when $i>j$. The following line is empty. The following $n$ lines are about the constraints on left vertices with an $n\times n$ matrix $A$. The $i$-th line contains a 01-string $A_i$ and the $j$-th character $A_{i,j}$ is $1$ if and only if $L_i$ and $L_j$ can't be both in $S$, which is the set of endpoints of the selected edges. We guarantee that $A_{i,i}$ ($1\leq i\leq n$) is $0$ and $A_{i,j}=A_{j,i}$ ($1\leq i,j\leq n$). The following line is about magic numbers containing $n$ integers. The $i$-th integer $M_i$ ($1\leq M_i\leq 100$) is the magic number of $L_i$.

For every case print a single line containing an integer, the minimum total cost. If it is impossible to get such a valid new graph, just output `-1` instead.

In the first case: :::align{center}  ::: We can choose edges $(L_1, R_1), (L_1, R_2), (L_2, R_3), (L_3, R_4)$ such that $S=\{L_1, L_2, L_3\}$, satisfies the $A$ matrix's constraints. And the degrees are $d_1=2, d_2=1, d_3=1$, so the total cost $=3^2 + 4^1 + 4^1 + 0 = 17$. In the second case, $R_3$ and $R_4$ can't be both covered at the same time, so there is no solution.