33OJ
登录 注册

#P17805. [ICPC 2019 Nanchang R] A Funny Bipartite Graph

[ICPC 2019 Nanchang R] A Funny Bipartite Graph

Problem Description

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 nn (1≤n≤181\leq n\leq 18) vertices, named L1,L2,⋯ ,LnL_1, L_2, \cdots, L_n. And the right part also has nn vertices, named R1,R2,⋯ ,RnR_1, R_2, \cdots, R_n.
  • LiL_i never connects with RjR_j when i>ji>j for all pairs of (i,j)(i,j) that 1≤i,j≤n1\leq i,j\leq n.
  • For each vertex on the left part LiL_i (1≤i≤n1\leq i\leq n), its degree DiD_i is at most 33 and at least 11 (1≤Di≤31\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×nn\times n matrix AA, Ai,jA_{i,j} is 11 if and only if LiL_i and LjL_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 LiL_i (1≤i≤n1\leq i\leq n) has a magic number MiM_i (1≤Mi≤1001\leq M_i\leq 100). If LiL_i appears in the new graph, its cost is Midi{M_i}^{d_i}, where did_i is the degree of LiL_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.

Input Format

There are several test cases in the input file. The first line contains one integer TT (1≤T≤101\leq T\leq 10) --- number of the test cases. For each case:

The first line contains one integer nn (1≤n≤181\leq n\leq 18) --- number of the left vertices.

The following nn lines are about the graph edges information with an n×nn\times n matrix GG. The ii-th line contains a 01-string GiG_i and the jj-th character Gi,jG_{i,j} is 11 if and only if LiL_i and RjR_j are connected, otherwise Gi,jG_{i,j} is 00. We guarantee that the degree of each left vertex LiL_i is between 11 and 33. We also guarantee that Gi,jG_{i,j} is always 00 when i>ji>j.

The following line is empty.

The following nn lines are about the constraints on left vertices with an n×nn\times n matrix AA. The ii-th line contains a 01-string AiA_i and the jj-th character Ai,jA_{i,j} is 11 if and only if LiL_i and LjL_j can't be both in SS, which is the set of endpoints of the selected edges. We guarantee that Ai,iA_{i,i} (1≤i≤n1\leq i\leq n) is 00 and Ai,j=Aj,iA_{i,j}=A_{j,i} (1≤i,j≤n1\leq i,j\leq n).

The following line is about magic numbers containing nn integers. The ii-th integer MiM_i (1≤Mi≤1001\leq M_i\leq 100) is the magic number of LiL_i.

Output Format

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.

2
4
1100
0110
0001
0001

0001
0001
0000
1100
3 4 4 5
4
1100
0110
0001
0001

0011
0001
1000
1100
3 4 4 5
17
-1

Hint

In the first case:

:::align{center} :::

We can choose edges (L1,R1),(L1,R2),(L2,R3),(L3,R4)(L_1, R_1), (L_1, R_2), (L_2, R_3), (L_3, R_4) such that S={L1,L2,L3}S=\{L_1, L_2, L_3\}, satisfies the AA matrix's constraints. And the degrees are d1=2,d2=1,d3=1d_1=2, d_2=1, d_3=1, so the total cost =32+41+41+0=17=3^2 + 4^1 + 4^1 + 0 = 17.

In the second case, R3R_3 and R4R_4 can't be both covered at the same time, so there is no solution.