P17805 [ICPC 2019 Nanchang R] A Funny Bipartite Graph

Bob 对二分图非常感兴趣，他需要你帮忙解决这个问题： :::align{center}  ::: Bob 有一个二分图，满足以下所有条件： - 左部有 $n$（$1\leq n\leq 18$）个顶点，记作 $L_1, L_2, \cdots, L_n$。右部同样有 $n$ 个顶点，记作 $R_1, R_2, \cdots, R_n$。 - 对于所有满足 $1\leq i,j\leq n$ 的数对 $(i,j)$，若 $i>j$，则 $L_i$ **绝不**与 $R_j$ 相连。 - 对于左部的每个顶点 $L_i$（$1\leq i\leq n$），其度数 $D_i$ 至多为 $3$ 且至少为 $1$（$1\leq D_i\leq 3$）。 Bob 希望从图中选出一些边，使得选出的边及其端点构成一个新图。然而，他必须遵守以下规则： - 某些顶点对不能同时出现在新图中。给定一个 $n\times n$ 的矩阵 $A$，$A_{i,j}=1$ 当且仅当 $L_i$ 和 $L_j$ 不能同时出现在新图中。 - Bob 必须保证选出的边覆盖所有右部顶点。也就是说，每个右部顶点都必须出现在新图中。 - 每个左部顶点 $L_i$（$1\leq i\leq n$）拥有一个魔力数 $M_i$（$1\leq M_i\leq 100$）。如果 $L_i$ 出现在新图中，其代价为 ${M_i}^{d_i}$，其中 $d_i$ 是 $L_i$ 在新图中的度数；否则其代价为 $0$。 现在 Bob 想要选出满足上述规则的边，使得总代价最小。请你编写一个程序，帮他求出最小总代价，或者判定无法得到一个合法的的新图。

输入文件包含多组测试数据。第一行包含一个整数 $T$（$1\leq T\leq 10$）—— 测试数据的组数。对于每组数据： 第一行包含一个整数 $n$（$1\leq n\leq 18$）—— 左部顶点的数量。 接下来的 $n$ 行通过一个 $n\times n$ 的矩阵 $G$ 描述了图的连边信息。第 $i$ 行包含一个 01 字符串 $G_i$，其第 $j$ 个字符 $G_{i,j}=1$ 当且仅当 $L_i$ 与 $R_j$ 是相连的，否则 $G_{i,j}=0$。我们保证每个左部顶点 $L_i$ 的度数介于 $1$ 和 $3$ 之间。同时保证当 $i>j$ 时，$G_{i,j}$ 总是 $0$。 接下来一行为空行。 接下来的 $n$ 行通过一个 $n\times n$ 的矩阵 $A$ 描述了左部顶点的限制条件。第 $i$ 行包含一个 01 字符串 $A_i$，其第 $j$ 个字符 $A_{i,j}=1$ 当且仅当 $L_i$ 和 $L_j$ 不能同时出现在 $S$ 中，这里 $S$ 是所选边的端点构成的集合。保证 $A_{i,i}$（$1\leq i\leq n$）为 $0$，且 $A_{i,j}=A_{j,i}$（$1\leq i,j\leq n$）。 接下来一行是魔力数，包含 $n$ 个整数。第 $i$ 个整数 $M_i$（$1\leq M_i\leq 100$）是 $L_i$ 的魔力数。

对于每组测试数据，输出一行一个整数，表示最小总代价。如果不可能得到合法的新图，则输出 `-1`。

在第一个样例中： :::align{center}  ::: 我们可以选出边 $(L_1, R_1), (L_1, R_2), (L_2, R_3), (L_3, R_4)$，使得 $S=\{L_1, L_2, L_3\}$，这满足矩阵 $A$ 的限制。并且各点度数分别为 $d_1=2, d_2=1, d_3=1$，因此总代价 $=3^2 + 4^1 + 4^1 + 0 = 17$。 在第二个样例中，$R_3$ 和 $R_4$ 无法同时被覆盖，所以无解。 翻译由 DeepSeek V4 Pro 完成