自动搬运

查看原文

来自洛谷，原作者为

	Acetyl Big Constant Generator Pro | 退役人

搬运于2025-08-24 22:30:35，当前版本为作者最后更新于2021-04-12 11:58:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先，这题的 $0 \le a_{i, j} \le 10^6$ 这个限制比较恶心，所以先不考虑这个限制，只需要找到一组合法的 $a$ 即可。这样问题就很简单了：钦定 $a$ 的最下面一行和最右边一列是 $0$，然后按照 $b$ 的限制从右下到左上一个个推即可。这部分时间复杂度可以做到 $\mathcal O(nm)$。

下面考虑调整这个 $a$ 矩阵的值，使得其对应的 $b$ 矩阵不变，但是每个 $a_{i, j}$ 的大小都在 $[0, 10^6]$ 之间。我们发现，对于一个 $x$，如果对一行的所有数字依次进行 $+x,-x,+x,-x,\dots$ 的操作，那么对应的 $b$ 矩阵不会发生变化，对于一列同理。下面就设 $r_i$ 为在第 $i$ 行上操作的 $x$ 值，设 $c_i$ 为在第 $i$ 列上操作的 $x$ 值。

现在，对于每个格子 $(i, j)$ 的值的限制，我们就可以将其转化为 $r_i$ 与 $c_i$ 的和或者差的限制。设 $A_{i, j}$ 表示 $(i, j)$ 格子增加的值，则 $A$ 矩阵如下：

$$\left( \begin{matrix} r_1+c_1 & -r_1+c_2 & r_1+c_3 & \cdots\\ r_2-c_1 & -r_2-c_2 & r_2-c_3 & \cdots\\ r_3+c_1 & -r_3+c_2 & r_3+c_3 & \cdots\\ \vdots & \vdots & \vdots & \ddots \end{matrix} \right) $$

对于一个位置 $a_{i, j}$，$A_{i, j}$ 必须满足 $-a_{i, j} \le A_{i, j} \le 10^6 - a_{i, j}$。

但是目前矩阵中值的形式很不统一，既有 $x+y$ 的形式也有 $x-y$ 的形式。考虑对于所有偶数的 $i$，将 $r_i$ 取相反数，对于所有奇数的 $j$，将 $c_j$ 取相反数，则 $A$ 矩阵就变成：

$$\left( \begin{matrix} r_1-c_1 & c_2-r_1 & r_1-c_3 & \cdots\\ c_1-r_2 & r_2-c_2 & c_3-r_2 & \cdots\\ r_3-c_1 & c_2-r_3 & r_3-c_3 & \cdots\\ \vdots & \vdots & \vdots & \ddots \end{matrix} \right) $$

这样矩阵中所有的值都变成 $x-y$ 的形式了，于是 $-a_{i, j} \le A_{i, j} \le 10^6 - a_{i, j}$ 就可以转化为 $-a_{i, j} \le x-y \le 10^6 - a_{i, j}$ 的形式，就变成了一个差分约束问题。

这个差分约束模型中共有 $n+m$ 个变量，有 $2nm$ 个约束，进行 SPFA 最短路的时间复杂度为 $\mathcal O(nm(n+m))$。但是，众所周知，SPFA 的复杂度永远是卡不满的（即使图中存在负环，即无解的情况，也只是部分点被松弛 $n + m$ 次），所以可以通过。

附上考场上写的代码：

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define loop(i, a) for (int i = 0; i < (a); ++i)
#define cont(i, a) for (int i = 1; i <= (a); ++i)
#define circ(i, a, b) for (int i = (a); i <= (b); ++i)
#define range(i, a, b, c) for (int i = (a); (c) > 0 ? (i <= (b)) : (i >= (b)); i += (c))
#define pub push_back
#define pob pop_back
#define mak make_pair
#define mkt make_tuple
typedef long long ll;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

int T;
int n, m;
int a[305][305], b[305][305];
vector<pair<int, int> > egs[605];
bool inq[605];
int tms[605];
ll dis[605];

void solve() {
	scanf("%d%d", &n, &m);
	cont(i, n - 1) cont(j, m - 1) scanf("%d", a[i] + j);
	memset(b, 0, sizeof(b));
	range(i, n, 1, -1) range(j, m, 1, -1) b[i][j] = a[i][j] - b[i + 1][j] - b[i + 1][j + 1] - b[i][j + 1];
	cont(i, n + m) egs[i].clear();
	cont(i, n) cont(j, m) {
		int mx = 1000000 - b[i][j], mn = -b[i][j];
		if (!((i + j) & 1)) egs[j + n].pub(mak(i, mx)), egs[i].pub(mak(j + n, -mn));
		else egs[j + n].pub(mak(i, -mn)), egs[i].pub(mak(j + n, mx));
	}
	deque<int> q;
	memset(inq, 0, sizeof(inq));
	memset(tms, 0, sizeof(tms));
	memset(dis, Inf, sizeof(dis));
	dis[1] = 0;
	q.pub(1);
	while (SZ(q)) {
		int now = q.front(); q.pop_front();
		++tms[now]; inq[now] = 0;
		if (tms[now] > n + m) {
			puts("NO");
			return;
		}
		loop(i, SZ(egs[now])) {
			int to = egs[now][i].first, siz = egs[now][i].second;
			if (dis[to] > dis[now] + siz) {
				dis[to] = dis[now] + siz;
				if (!inq[to]) {
					if (SZ(q) && dis[to] < dis[q[0]]) q.push_front(to);
					else q.pub(to);
					inq[to] = 1;
				}
			}
		}
	}
	cont(i, n) cont(j, m) {
		if ((i + j) & 1) b[i][j] -= dis[i];
		else b[i][j] += dis[i];
		if ((i + j) & 1) b[i][j] += dis[j + n];
		else b[i][j] -= dis[j + n];
	}
	puts("YES");
	cont(i, n) cont(j, m) printf("%d%c", b[i][j], " \n"[j == m]);
}

int main() {
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}