题解：P3208 [HNOI2010] 矩阵

· · 题解

这是一篇差分约束题解，代码特别简单，时间复杂度 \Theta((n+m)^3) + O((n+m)^2 p)。理论上是最优解，不过这题 p 小，所以对比其他做法显得常数大。建议加强数据，把 p 开大点。

令 A = \{a_{i,j}\} 为答案矩阵，S = \{s_{i,j}\} 为每个 2 \times 2 的子矩阵和。

注意到当 i \ge 2 且 j \ge 2 时，a_{i,j} = s_{i,j} - a_{i,j-1} - a_{i-1,j} - a_{i-1,j-1}，所以确定 A 的第一行和第一列就能唯一得到一组解。

故只要在 a_{1, j} 和 a_{i, 1} 的位置上依次贪心，枚举取值，每次判断是否有解即可。

先令 A 的第一行第一列全为 0，求出一组特解，记为 B = \{b_{i,j}\}，则对任意的 A，都存在 r_i, c_j 使得 a_{i,j} = b_{i,j} + (-1)^{i+j} (r_i - c_j)。

::::info[感性理解]

首先，我们把 a_{i, j}, a_{i,j-1}, a_{i-1,j}, a_{i-1,j-1} 加起来，会发现 r 和 c 全消掉了，这显然是满足 S 的约束的。

其次，r_i 和 c_j 本质上是 A 第一行第一列的数的线性组合，所以一定存在这样的 r 和 c。

::::

根据前面的推导，A 有解等价于存在 r_i, c_j 满足 0 \le b_{i,j} + (-1)^{i+j} (r_i - c_j) < p，一共 n+m 个变量，若干个不等式作为约束条件，这很差分约束啊！

每次贪心都跑暴力做一遍差分约束，显然会 T 飞，但考虑到贪心的本质是每次增加 b_{i,j} + (-1)^{i+j}(r_i - c_j) = k 的约束条件，即加两条边并判断是否有负环，那直接 Floyd 就做完了。

具体来说，我们先 \Theta((n+m)^3) 求一遍全源最短路，每次加边后 \Theta(n+m) 判断是否有负环，如果没有则记录答案并 \Theta((n+m)^2) 更新全源最短路。总复杂度 \Theta((n+m)^3) + O((n+m)^2 p)。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 405;

int n, m, p, a[N][N], b[N][N], s[N][N], dis[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> s[i][j];
            if (i >= 2 && j >= 2) {
                b[i][j] = s[i][j] - b[i][j - 1] - b[i - 1][j] - b[i - 1][j - 1];
            }
        }
    }

    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n + m; i++) {
        dis[i][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int u = i, v = j + n;
            if ((i + j) % 2) {
                swap(u, v);
            }
            dis[u][v] = min(dis[u][v], b[i][j]);                            // u - v + b[i][j] >= 0
            dis[v][u] = min(dis[v][u], p - 1 - b[i][j]);                    // u - v + b[i][j] <= p - 1
        }
    }
    for (int k = 1; k <= n + m; k++) {
        for (int i = 1; i <= n + m; i++) {
            for (int j = 1; j <= n + m; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i >= 2 && j >= 2) {
                a[i][j] = s[i][j] - a[i][j - 1] - a[i - 1][j] - a[i - 1][j - 1];
                continue;
            }
            int u = i, v = j + n;
            if ((i + j) % 2) {
                swap(u, v);
            }
            for (int k = 0; k < p; k++) {
                int w1 = k + b[i][j];                                       // u - v + b[i][j] >= k
                int w2 = k - b[i][j];                                       // u - v + b[i][j] <= k
                bool f = false;
                for (int x = 1; x <= n + m && !f; x++) {
                    f = min(dis[x][u] + w1 + dis[v][x], dis[x][v] + w2 + dis[u][x]) < 0;
                } 
                if (!f) {
                    a[i][j] = k;
                    for (int x = 1; x <= n + m; x++) {
                        for (int y = 1; y <= n + m; y++) {
                            dis[x][y] = min(dis[x][y], min(dis[x][u] + w1 + dis[v][y], dis[x][v] + w2 + dis[u][y]));
                        }
                    }
                    break;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << a[i][j] << " \n"[j == m];
        }
    }
    return 0;
}