#P17805. [ICPC 2019 Nanchang R] A Funny Bipartite Graph
[ICPC 2019 Nanchang R] A Funny Bipartite Graph
题目描述
Bob 对二分图非常感兴趣,他需要你帮忙解决这个问题:
:::align{center}
:::
Bob 有一个二分图,满足以下所有条件:
- 左部有 ()个顶点,记作 。右部同样有 个顶点,记作 。
- 对于所有满足 的数对 ,若 ,则 绝不与 相连。
- 对于左部的每个顶点 (),其度数 至多为 且至少为 ()。
Bob 希望从图中选出一些边,使得选出的边及其端点构成一个新图。然而,他必须遵守以下规则:
- 某些顶点对不能同时出现在新图中。给定一个 的矩阵 , 当且仅当 和 不能同时出现在新图中。
- Bob 必须保证选出的边覆盖所有右部顶点。也就是说,每个右部顶点都必须出现在新图中。
- 每个左部顶点 ()拥有一个魔力数 ()。如果 出现在新图中,其代价为 ,其中 是 在新图中的度数;否则其代价为 。
现在 Bob 想要选出满足上述规则的边,使得总代价最小。请你编写一个程序,帮他求出最小总代价,或者判定无法得到一个合法的的新图。
输入格式
输入文件包含多组测试数据。第一行包含一个整数 ()—— 测试数据的组数。对于每组数据:
第一行包含一个整数 ()—— 左部顶点的数量。
接下来的 行通过一个 的矩阵 描述了图的连边信息。第 行包含一个 01 字符串 ,其第 个字符 当且仅当 与 是相连的,否则 。我们保证每个左部顶点 的度数介于 和 之间。同时保证当 时, 总是 。
接下来一行为空行。
接下来的 行通过一个 的矩阵 描述了左部顶点的限制条件。第 行包含一个 01 字符串 ,其第 个字符 当且仅当 和 不能同时出现在 中,这里 是所选边的端点构成的集合。保证 ()为 ,且 ()。
接下来一行是魔力数,包含 个整数。第 个整数 ()是 的魔力数。
输出格式
对于每组测试数据,输出一行一个整数,表示最小总代价。如果不可能得到合法的新图,则输出 -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}
:::
我们可以选出边 ,使得 ,这满足矩阵 的限制。并且各点度数分别为 ,因此总代价 。
在第二个样例中, 和 无法同时被覆盖,所以无解。
翻译由 DeepSeek V4 Pro 完成