『省选联考 2021 A 卷』矩阵游戏的题解

MoonPie · 2021-04-13 13:31:18 · 题解

题意

有一个 n\times m 的矩阵 A，给出一个 (n-1)\times(m-1) 矩阵 B，满足：

问你是否存在 A 满足所有的 0\le a_{i,j} \le 10^6。

题解

首先，可以很容易地构造出一个只满足 b_{i,j} 限制的 A。然后，考虑如何修改可以让 A 在满足 b 的条件的同时满足范围条件。 我们发现如果只给 A 矩阵的一行或一列进行 +1,-1,+1,-1,\dots 的操作后，每一个田字格的和仍保持不变。

所以，我们根据每个 a_{i.j} 的范围限制可以列出不等式：

然而这并不仅有我们熟知的 差分约束 ，还有 “和分约束”，怎么办呢？

之所以会出现和，是因为有些地方行列的符号相同。解决方案就是：

类似两种不同的黑白格染色，就使得每个位置的符号都不相同了，也就转化成了差分约束。

实现细节

由于我们建的图是一张完全图，边数多，\mathrm{SPFA} 的实现有队列，寻址不连续，比较卡常。 不如直接用 \mathrm{Bellman-Ford} 常数小。

一个问题

还有一个疑问，也是大部分题解中没有说明的一点，就是： 是否只要有这两个操作就可以让矩阵 A 达到所有可以达到（且合法）的状态吗？答案是肯定的。

证明如下：

引理：如果一个 A 矩阵确定了第一行和第一列的全部元素，那么这个矩阵是确定的。 证明：原有 (n-1)\times(m-1) 个方程，后来再加 n+m-1 个方程总共就是 n\times m 个方程恰好可以解出 A 矩阵中的 n\times m 个元素。

我们的两种修改操作由于每次修改一行或一列，如果先改第一行再改第一列，就显然可以把 A 矩阵的第一行和第一列修改为我们想要的任意状态，所以根据引理，原命题得证。

代码

#define ll long long
const ll inf = 1e18;
const int N = 305, MX = 1000000;
int n,m;
ll a[N][N],b[N][N];

int id(int x,int y) { return (x-1)*n+y; }

namespace diff {
    struct edge {int to,w; };
    ll c[N*2],g[N*2][N*2];

    void init() {
    for(int i = 0; i <= n+m; ++i) {
        for(int j = 0; j <= n+m; ++j) {
            diff::g[i][j] = inf;
        }
    }
    }
    void adde(int u,int v,int w) { g[u][v] = w; }
    bool run() {
        memset(c,0x3f,sizeof(c));
        c[0] = 0;
        for(int i = 1; i <= n+m; ++i) g[0][i] = 0;
        int ti,l,r;
        for(ti = 1; ti <= n+m+1; ++ti) {
            int rel = 0;
            for(int u = 0; u <= n+m; ++u) {
                if(u == 0) l = 1, r = n+m;
                else if(u <= n) l = n+1, r = n+m;
                else l = 1, r = n;
                for(int v = l; v<= r; ++v) {
                    rel |= umin(c[v], c[u]+g[u][v]);
                }
            }
            if(!rel) break;
        }
        return ti < n+m+1;
    }
    void output() {
        puts("YES");
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                if((i+j)&1) a[i][j] = a[i][j] + c[i] - c[n+j];
                else a[i][j] = a[i][j] - c[i] + c[n+j];
                printf("%lld ",a[i][j]);
            }
            puts("");
        }
    }
}

signed main()
{
  int T; read(T);
  for(int cs = 1; cs <= T; ++cs) {

    read(n); read(m);
    diff::init();
    for(int i = 1; i < n; ++i) for(int j = 1; j < m; ++j) read(b[i][j]);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) a[i][j] = 0;
    }

    for(int i = 2; i <= n; ++i) {
        for(int j = 2; j<= m; ++j) {
            a[i][j] = b[i-1][j-1] - a[i-1][j] - a[i][j-1] - a[i-1][j-1];
        }
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if((i+j)&1) {
                diff::adde(i,j+n,a[i][j]);
                diff::adde(j+n,i,MX-a[i][j]);
            }
            else {
                diff::adde(i,j+n,MX-a[i][j]);
                diff::adde(j+n,i,a[i][j]);
            }
        }
    }

    if(!diff::run()) puts("NO");
    else diff::output();

  }

    return 0;
}