{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n\u003cp\u003eBob对二分图非常感兴趣,他需要帮助解决这个问题:\u003c/p\u003e\n\u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/8f510ff9982348240b85e2d1df8c5426?v\u003d1666305101\" alt\u003d\"\"\u003e\u003c/p\u003e\n\u003cp\u003eBob有一个二分图,满足以下所有条件:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e左边部分有$n$ ($1\\leq n\\leq 18$)个顶点,命名为$L_1,L_2,\\cdots,L_n$。右边部分也有$n$个顶点,命名为$R_1,R_2,\\cdots,R_n$。\u003c/li\u003e\n \u003cli\u003e当$i\u0026gt;j$时,对于所有的$(i,j)$对,$L_i$ \u003cstrong\u003e从不\u003c/strong\u003e与$R_j$连接,其中$1\\leq i,j\\leq n$。\u003c/li\u003e\n \u003cli\u003e对于左边部分的每个顶点$L_i$ ($1\\leq i\\leq n$),其度数$D_i$最多为$3$,最少为$1$ ($1\\leq D_i\\leq 3$)。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eBob想从图中选择一些边,使得所选边和它们的端点形成一个新的图。然而,他应遵守以下规则:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e一些顶点对不能同时出现在新图中。你将得到一个$n\\times n$矩阵$A$,当且仅当$L_i$和$L_j$不能同时出现在新图中时,$A_{i,j}$为$1$。\u003c/li\u003e\n \u003cli\u003eBob必须确保所选的边覆盖所有的右顶点。换句话说,每个右顶点都应出现在新图中。\u003c/li\u003e\n \u003cli\u003e每个左顶点$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$在新图中的度数,否则其成本为零。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e现在Bob想选择满足上述规则的边,以最小的总成本。请编写一个程序帮助他找到最小的总成本,或者确定无法得到这样一个有效的新图。\u003c/p\u003e\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e输入文件中有几个测试用例。第一行包含一个整数$T$ ($1\\leq T\\leq 10$) --- 测试用例的数量。对于每个用例:\u003c/p\u003e\n\u003cp\u003e第一行包含一个整数$n$ ($1\\leq n\\leq 18$) --- 左顶点的数量。\u003c/p\u003e\n\u003cp\u003e接下来的$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\u0026gt;j$时,$G_{i,j}$总是$0$。\u003c/p\u003e\n\u003cp\u003e接下来的一行是空的。\u003c/p\u003e\n\u003cp\u003e接下来的$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}\u003dA_{j,i}$ ($1\\leq i,j\\leq n$)。\u003c/p\u003e\n\u003cp\u003e接下来的一行包含$n$个整数。第$i$个整数$M_i$ ($1\\leq M_i\\leq 100$)是$L_i$的魔法数。\u003c/p\u003e\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cp\u003e对于每个用例,打印一行包含一个整数,即最小的总成本。如果无法得到这样一个有效的新图,就输出\u003ccode\u003e-1\u003c/code\u003e。\u003c/p\u003e\n"}},{"title":"样例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n1100\n0110\n0001\n0001\n\n0001\n0001\n0000\n1100\n3 4 4 5\n4\n1100\n0110\n0001\n0001\n\n0011\n0001\n1000\n1100\n3 4 4 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e\u003cp\u003e在第一个案例中:\u003c/p\u003e\u003cp\u003e\u003cimg src\u003d\"https://res.jisuanke.com/img/upload/20191114/f7f7ad711042cdac7975f0fd708c2659eb124377.png\" alt\u003d\"\"\u003e\u003c/p\u003e\u003cp\u003e我们可以选择边$(L_1,R_1),(L_1,R_2),(L_2,R_3),(L_3,R_4)$,使得$S\u003d\\{L_1,L_2,L_3\\}$,满足$A$矩阵的约束。度数为$d_1\u003d2,d_2\u003d1,d_3\u003d1$,所以总成本$\u003d3^2 + 4^1 + 4^1 + 0 \u003d 17$。\u003c/p\u003e\u003cp\u003e在第二个案例中,$R_3$和$R_4$不能同时被覆盖,所以没有解决方案。\u003c/p\u003e"}}]}