P7515 [省选联考 2021 A 卷] 矩阵游戏 题解

首先，这题的 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 矩阵如下：

对于一个位置 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 矩阵就变成：

这样矩阵中所有的值都变成 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;
}