#553. 【2024-11-23 P3】基础矩阵问题

【2024-11-23 P3】基础矩阵问题

当前没有测试数据。

题目描述

提示:题目描述中的“向量“可以理解为一个数组。

小圈是一名运筹学大师。她正在研究如下问题:

给定 mm 维 01 空间内 nn 个约束,满足 AX=bAX = b,和一个 mm 维系数向量 C∈RmC \in R^{m}。你要找到一个满足约束的 mm 维列向量 XX,最大化 C⋅XC \cdot X。

这个问题是一个过于普通的 01 整数规划问题,小圈同学已经提出了一个关于 nn 和 mm 的多项式算法来解决它。在论文写作过程中,小圈同学尝试展望一个更新的问题,即把限制组成的非齐次线性方程组改为模 22 意义下的方程组。这下小圈不会了,所以请你来解决这个问题。

给定一个 nn 行 mm 列的矩阵 an×ma_{n \times m},一个 nn 维列向量 b=[b1,b2,…bn]Tb=[b_1, b_2, \dots b_n]^T,和一个 mm 维系数向量 C=[c1,c2,…cm]TC=[c_1,c_2,\dots c_m]^T,其中 ai,j∈{0,1}a_{i,j} \in \{0,1\},bi∈{0,1}b_i \in \{0,1\},ci∈[1,109]∩Zc_i \in [1, 10^9] \cap \Z。你要找到一个 mm 维列向量 X=[x1,x2,…xm]TX = [x_1, x_2, \dots x_m]^T,其中 xi∈{0,1}x _ i \in \{0, 1\},并且满足:

  • $b_i \equiv \sum_{j = 1}^m a_{i,j}\times x_j \pmod 2$,i=1,2,3,…,ni = 1,2,3,\dots , n。

最大化 ∑j=1mcjxj\sum_{j = 1}^m c_j x_j,输出方案。

输入格式

本题单个测试点内有多组测试数据。第一行是一个整数 TT,表示数据组数。对每组数据,按如下格式输入:

第一行是两个整数,表示 n,mn,m。
接下来 nn 行,每行 mm 个整数,表示矩阵 an×ma_{n\times m}。
接下来一行 nn 个整数,表示 b1,b2,…bnb_1, b_2, \dots b_n。
接下来一行 mm 个整数,表示 c1,c2,…cmc_1, c_2, \dots c_m。

输出格式

对每组数据,按如下格式输出:

  • 如果不存在符合要求的 XX,输出一行一个字符串 −1-1。
  • 否则在第一行输出最大的 ∑j=1mcjxj\sum_{j = 1}^m c_j x_j,第二行输出 mm 个整数,第 ii 个整数表示最大化方案里 xix_i 的值。

样例

样例 1 输入

3
2 2
0 1
1 0
1 1
1 1
2 2
0 0
1 1
1 1
1 1
2 2
0 0
1 1
0 1
1 10

样例 1 输出

2
1 1
-1
10
0 1

样例 2

见下发文件 matrix2.in 和 matrix2.ans,该样例满足测试点 1∼21 \sim 2 的限制。

数据范围和约定

本题共包含 1010 个测试点,每个测试点 1010 分。

测试点编号 特殊限制
1∼21 \sim 2 m≤20m \le 20
3∼53 \sim 5 m≤40m \le 40
6∼86 \sim 8 n≤20n \le 20
9∼109 \sim 10 无特殊限制

对 100%100\% 的数据,1≤n,m≤601 \leq n, m \leq 60,1≤n+m≤601 \leq n + m \leq 60,1≤T≤51 \leq T \leq 5,0≤ai,j,bi≤10 \leq a_{i,j}, b_i \leq 1,1≤ci≤1091 \leq c_i \leq 10^9。