题解：P10644 [NordicOI 2022] 能源网格 Power Grid

hhoppitree · 2024-08-28 10:32:12 · 题解

记行和为 R_i，列和为 C_i，容易证明 \sum R=\sum C 则必有对应解，记 p 为输入元素不全相同的一行，q 为输入元素不全相同的一列（若不存在则为 0，否则任意），若 p=q=0 是平凡的（此时必有 R_1=R_2=\cdots 或 C_1=C_2=\cdots），下文讨论 p+q\ne0 的情况，在下文推导中，我们将多次用到如下事实：\{x_1-y_1,x_1+y_1\}=\{x_2-y_2,x_2+y_2\}\Leftrightarrow x_1=x_2,y_1=y_2，即若 (x_1,y_1)\ne(x_2,y_2)，则对应的集合交的大小 \le1。

若 pq\ne0，我们取出 (p,q) 和 (r,q)，其中 r 为第 q 列任一与 (p,q) 值不同的位置，先令 C_q=0，枚举 4 种可能的 R_p 与 R_r，则由 R_p\ne R_r，可推理出全部 C_{*}，进而得出所有 R_{*}，最终使用全局加上同样的数来调整 \sum R-\sum C。

考虑拓展这个做法，不妨设 p=0,q\ne0，发现此时可能出现 C_{*} 全相同的情况导致无法推理出 R_{*}（由于第 p 行有至少两种取值，故 C_{*} 不会全相同），可以证明此时 C_{*} 必然全相同，而每个 R_{i} 都是在一个大小为 2 的集合中选择，使用 \texttt{bitset} 优化背包计算出所有可能的 \sum R 后选出一种合理的进行调整即可，时间复杂度为 \mathcal{O}\left(\dfrac{n^2V}{w}\right)。