33OJ
登录 注册

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

[ICPC 2019 Nanchang R] A Funny Bipartite Graph

题目描述

Bob 对二分图非常感兴趣,他需要你帮忙解决这个问题:

:::align{center} :::

Bob 有一个二分图,满足以下所有条件:

  • 左部有 nn(1≤n≤181\leq n\leq 18)个顶点,记作 L1,L2,⋯ ,LnL_1, L_2, \cdots, L_n。右部同样有 nn 个顶点,记作 R1,R2,⋯ ,RnR_1, R_2, \cdots, R_n。
  • 对于所有满足 1≤i,j≤n1\leq i,j\leq n 的数对 (i,j)(i,j),若 i>ji>j,则 LiL_i 绝不与 RjR_j 相连。
  • 对于左部的每个顶点 LiL_i(1≤i≤n1\leq i\leq n),其度数 DiD_i 至多为 33 且至少为 11(1≤Di≤31\leq D_i\leq 3)。

Bob 希望从图中选出一些边,使得选出的边及其端点构成一个新图。然而,他必须遵守以下规则:

  • 某些顶点对不能同时出现在新图中。给定一个 n×nn\times n 的矩阵 AA,Ai,j=1A_{i,j}=1 当且仅当 LiL_i 和 LjL_j 不能同时出现在新图中。
  • Bob 必须保证选出的边覆盖所有右部顶点。也就是说,每个右部顶点都必须出现在新图中。
  • 每个左部顶点 LiL_i(1≤i≤n1\leq i\leq n)拥有一个魔力数 MiM_i(1≤Mi≤1001\leq M_i\leq 100)。如果 LiL_i 出现在新图中,其代价为 Midi{M_i}^{d_i},其中 did_i 是 LiL_i 在新图中的度数;否则其代价为 00。

现在 Bob 想要选出满足上述规则的边,使得总代价最小。请你编写一个程序,帮他求出最小总代价,或者判定无法得到一个合法的的新图。

输入格式

输入文件包含多组测试数据。第一行包含一个整数 TT(1≤T≤101\leq T\leq 10)—— 测试数据的组数。对于每组数据:

第一行包含一个整数 nn(1≤n≤181\leq n\leq 18)—— 左部顶点的数量。

接下来的 nn 行通过一个 n×nn\times n 的矩阵 GG 描述了图的连边信息。第 ii 行包含一个 01 字符串 GiG_i,其第 jj 个字符 Gi,j=1G_{i,j}=1 当且仅当 LiL_i 与 RjR_j 是相连的,否则 Gi,j=0G_{i,j}=0。我们保证每个左部顶点 LiL_i 的度数介于 11 和 33 之间。同时保证当 i>ji>j 时,Gi,jG_{i,j} 总是 00。

接下来一行为空行。

接下来的 nn 行通过一个 n×nn\times n 的矩阵 AA 描述了左部顶点的限制条件。第 ii 行包含一个 01 字符串 AiA_i,其第 jj 个字符 Ai,j=1A_{i,j}=1 当且仅当 LiL_i 和 LjL_j 不能同时出现在 SS 中,这里 SS 是所选边的端点构成的集合。保证 Ai,iA_{i,i}(1≤i≤n1\leq i\leq n)为 00,且 Ai,j=Aj,iA_{i,j}=A_{j,i}(1≤i,j≤n1\leq i,j\leq n)。

接下来一行是魔力数,包含 nn 个整数。第 ii 个整数 MiM_i(1≤Mi≤1001\leq M_i\leq 100)是 LiL_i 的魔力数。

输出格式

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

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

提示

在第一个样例中:

:::align{center} :::

我们可以选出边 (L1,R1),(L1,R2),(L2,R3),(L3,R4)(L_1, R_1), (L_1, R_2), (L_2, R_3), (L_3, R_4),使得 S={L1,L2,L3}S=\{L_1, L_2, L_3\},这满足矩阵 AA 的限制。并且各点度数分别为 d1=2,d2=1,d3=1d_1=2, d_2=1, d_3=1,因此总代价 =32+41+41+0=17=3^2 + 4^1 + 4^1 + 0 = 17。

在第二个样例中,R3R_3 和 R4R_4 无法同时被覆盖,所以无解。

翻译由 DeepSeek V4 Pro 完成