题目理解

我们有一个 $n \times m$ 的矩阵 $a_{i,j}$（每个元素是非负整数且 $\le 10^6$），Bob 根据它生成了一个 $(n-1) \times (m-1)$ 的矩阵 $b_{i,j}$，其中：

$$b_{i,j} = a_{i,j} + a_{i,j+1} + a_{i+1,j} + a_{i+1,j+1} $$

现在给出 $b_{i,j}$，要求还原出 $a_{i,j}$。如果不可行，输出 NO；如果可行，输出 YES 和任意一个满足条件的 $a$ 矩阵。

---

关键观察

1. 问题的线性特性

这是一个线性方程组问题：对于 $(n-1)\times(m-1)$ 个方程，要求 $n\times m$ 个未知数。由于方程数少于未知数个数，通常会有无穷多解（如果存在解的话）。

2. 变量自由度的分析

• 总未知数：$n \times m$
• 方程数：$(n-1) \times (m-1)$
• 自由变量数：$n \times m - (n-1) \times (m-1) = n + m - 1$

这表明我们可以先固定 $n+m-1$ 个变量的值，然后通过方程组唯一确定其他变量。

---

算法设计

1. 基础构造

我们可以先固定最后一行和最后一列的值为 0：

• $a_{i,m} = 0$ $(1 \le i \le n)$
• $a_{n,j} = 0$ $(1 \le j \le m)$

然后从右下角开始递推：

$$a_{i,j} = b_{i,j} - a_{i,j+1} - a_{i+1,j} - a_{i+1,j+1} $$

这样我们得到了一个初始解 $a^{(0)}_{i,j}$。

2. 解的调整

观察发现，如果我们将矩阵进行"黑白染色"（类似国际象棋棋盘），对每个黑格加上 $x$，对每个白格减去 $x$，那么每个 $b_{i,j}$ 的值不会改变（因为每个 $2\times2$ 子矩阵包含两个黑格和两个白格）。

具体来说，对于位置 $(i,j)$：

• 如果 $(i+j)$ 是奇数：$a_{i,j} = a^{(0)}_{i,j} - r_i + c_j$
• 如果 $(i+j)$ 是偶数：$a_{i,j} = a^{(0)}_{i,j} + r_i - c_j$

这里 $r_i$ $(1 \le i \le n)$ 和 $c_j$ $(1 \le j \le m)$ 是我们引入的调整变量，但其中有一个自由度是冗余的（整体平移不变），实际自由度为 $n+m-1$。

3. 约束转化为差分约束系统

我们需要确保所有 $a_{i,j}$ 满足 $0 \le a_{i,j} \le 10^6$。

对于每个位置 $(i,j)$：

• 如果 $(i+j)$ 是奇数：$0 \le a^{(0)}_{i,j} - r_i + c_j \le 10^6$
• 如果 $(i+j)$ 是偶数：$0 \le a^{(0)}_{i,j} + r_i - c_j \le 10^6$

这可以重写为：

• 如果 $(i+j)$ 是奇数：
  • $r_i - c_j \le a^{(0)}_{i,j}$
  • $c_j - r_i \le 10^6 - a^{(0)}_{i,j}$
• 如果 $(i+j)$ 是偶数：
  • $c_j - r_i \le a^{(0)}_{i,j}$
  • $r_i - c_j \le 10^6 - a^{(0)}_{i,j}$

4. 构建图模型

我们将 $r_i$ 和 $c_j$ 看作图中的节点：

• $n$ 个 $r$ 节点：编号 $1$ 到 $n$
• $m$ 个 $c$ 节点：编号 $n+1$ 到 $n+m$

不等式 $x - y \le d$ 对应于从 $y$ 到 $x$ 的一条有向边，权值为 $d$。

5. 求解差分约束系统

使用 Bellman-Ford 或 SPFA 算法判断是否存在解。如果存在负环，则无解；否则，我们可以得到一组 $r_i$ 和 $c_j$ 的值，进而计算出最终的 $a_{i,j}$。

由于题目只需要任意一组解，我们可以固定 $r_1 = 0$ 作为起点。

---

算法正确性

1. 构造的完备性

我们的构造方法涵盖了所有可能的调整：任何满足 $b$ 矩阵的 $a$ 矩阵都可以表示为 $a^{(0)}$ 加上某种棋盘格调整。

2. 范围约束的充分性

差分约束系统完整编码了所有 $0 \le a_{i,j} \le 10^6$ 的条件，因此得到的解一定满足要求。

3. 解的存在性判断

差分约束系统无解当且仅当图中存在负环，这对应了原始问题无解的情况。

---

复杂度分析

时间复杂度

1. 构造初始解：$O(nm)$
2. 建图：$O(nm)$ 条边
3. SPFA：最坏 $O(nm \cdot (n+m))$，但由于图比较稀疏，实际运行很快

对于 $n,m \le 300$，总复杂度可以接受。

空间复杂度

• 存储矩阵：$O(nm)$
• 存储图：$O(nm)$ 条边

---

代码实现要点

1. 变量定义

const int MAXN = 300;
int n, m;
int a[MAXN+5][MAXN+5], b[MAXN+5][MAXN+5];
vector<pair<int, int>> E[MAXN*2+5];  // 邻接表

2. 关键步骤

1. 读取输入，构造初始解 $a^{(0)}$
2. 根据 $(i+j)$ 的奇偶性建立差分约束图
3. 使用 SPFA 判断负环
4. 输出结果或 "NO"

3. 注意事项

• 需要处理多组测试数据
• 注意数组大小（$n+m$ 个节点）
• 注意边界条件

---

算法标签

• 差分约束
• 最短路
• 构造

---

总结

本题通过巧妙的"黑白染色"观察，将矩阵还原问题转化为差分约束系统问题。算法充分利用了 $b$ 矩阵的线性特性，通过固定部分变量和引入调整参数，将范围约束转化为图中的边权约束，最终通过最短路算法求解。

这种方法不仅能够判断解的存在性，还能构造出具体的解，完美满足了题目要求。