「联合省选2021」矩阵游戏-LOJ3500

上帝给了我 20 分，却又给了别人 20 分，ん？

Description

对于一个 $n\times m$ 的矩阵 $a_{i,j}$ ，定义大小为 $(n - 1)\times (m-1)$ 的矩阵 $b_{i,j}$ 为

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

其中 $n,m\ge2$

现给定矩阵 $b$，构造一个矩阵 $a$，$T$ 组数据

$n\le500,T\le10\\b_{i,j}\le4\times 10^6,0\le a_{i,j}\le 10^6$

Solution

首先发现很容易构造一个矩阵 $a’$ 满足 $b$ 的限制，但是不满足 $0\le a_{i,j}\le10^6$ 的限制，构造也很简单，我们把 $a’$ 第一行第一列都填 0，剩下的位置就可以递推出来。现在考虑我们通过调整法，尝试使得这个矩阵的每个元素合法。

经过简单手玩，我们发现如果我们对矩阵做如下操作

$$\begin{bmatrix} &+x &-x &+x &\cdots &-x\\ &0 &0 &\cdots &0 &0\\ &0 &0 &\ddots &0 &0\\ &0 &0 &\cdots &0 &0\\ \end{bmatrix} 或 \begin{bmatrix} &-x &0 &\cdots &0 &0\\ &+x &0 &\cdots &0 &0\\ &-x &0 &\ddots &0 &0\\ &+x &0 &\cdots &0 &0\\ \end{bmatrix}$$

每个田字格里的数字和不会改变。

于是我们通过一通操作后，设 $r_i$ 为 $i$ 行做的操作的值，$c_i$ 为第 $i$ 列做的操作的值，于是最终的矩阵长成这样

$$\begin{bmatrix} &a_{1,1}+r1-c1 &a_{1,2}-r1-c2 &a_{1,3}+r1-c3 &\cdots\\ &a_{2,1}+r2+c1 &a_{2,2}-r2+c2 &a_{3,3}+r2+c3 &\cdots\\ &a_{3,1}+r3-c1 &a_{2,2}-r3-c2 &a_{3,3}+r3-c3 &\cdots\\ &\vdots \end{bmatrix}$$

由于 $a_{i,j}$ 是已知的值，所以现在的限制变成了

$$0\le a_{i,j} \pm r_i \pm c_j \le 10^6\\ 0-a_{i,j}\le \pm r_i \pm c_j\le 10^6 - a_{i,j}$$

但是还是不大可做，但是我们观察到如果里面的限制系数一正一负，那么这个限制就是一个差分约束，可以容易的解决，现在考虑如何把这个限制转化成这样；

实际上我们只需要设 $r’_i = (-1)^ir_i$ ，$c’j$ 同理，然后原本的限制就变成了

$$0-a_{i,j}\le \pm (r'_i - 'c_j) \le 10^6 - a_{i,j}$$

于是就变成差分约束了，直接 spfa 信仰一波就过了，复杂度上限应该是 $O(n^2m)$ （$n,m$ 为图中点数和边数），但是跑的很快，芜湖。

从洛谷偷个图

Code

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (ll i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((ll)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <ll, ll> pii ;
typedef vector <ll> vi ;
typedef vector <pii> vii ;
typedef queue <ll> qi ;
typedef queue <pii> qii ;
typedef set <ll> si ;
typedef map <ll, ll> mii ;
typedef map <string, ll> msi ;
const ll maxn = 5e3 + 100 ;
const ll inf = 0x3f3f3f3f ;
const ll iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 998244353 ;
const double eps = 1e-7 ;
template <class T = ll> T chmin(T &a, T b) { return a = min(a, b);}
template <class T = ll> T chmax(T &a, T b) { return a = max(a, b);}
template <class T = ll> iv red(T &x) { x -= mod, x += x >> 31 & mod;}
template <class T = ll> T read()
{
    T f = 1, a = 0;
    char ch = getchar() ;
    while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
    while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
    return a * f ;
}

ll t;

ll n, m;

ll b[maxn][maxn], a[maxn][maxn];

void build()
{
    rep(i, 1, n) a[i][1] = 0;
    rep(i, 1, m) a[1][i] = 0;
    rep(i, 2, n) rep(j, 2, m) a[i][j] = b[i - 1][j - 1] - a[i - 1][j - 1] - a[i - 1][j] - a[i][j - 1];
}

namespace spfa
{
    ll n;
    qi q;
    vii edge[maxn];
    ll sum[maxn], dist[maxn], inque[maxn];
    void clear()
	{
        rep(i, 0, n) vii().swap(edge[i]);
        while(!q.empty()) q.pop();
        n = 0;
    }
    void add(ll u, ll v, ll w)
	{
        // printf("%lld -> %lld : %lld\n", u, v, w);
        edge[u].pb(mp(v, w));
    }
    ll work()
	{
        rep(i, 0, n) dist[i] = linf, sum[i] = 0, inque[i] = 0;
        dist[0] = 0;
        q.push(0);
        inque[0] = 1;
        sum[0] = 1;
        while(!q.empty())
        {
            ll now = q.front();
            q.pop();
            inque[now] = 0;
            // printf("spfa : %lld : %lld\n", now, dist[now]);
            for(pii to : edge[now])
            {
                if(dist[to.fi] > dist[now] + to.se)
                {
                    dist[to.fi] = dist[now] + to.se;
                    if(!inque[to.fi])
                    {
                        q.push(to.fi), inque[to.fi] ++;
                        sum[to.fi] ++;
                        if(sum[to.fi] > n) return 0;
                    }
                }
            }
        }
        return 1;
    }
}

ll pos[2][maxn];

void rebuild()
{
    spfa :: clear();

    rep(i, 1, n) pos[0][i] = ++ spfa :: n, spfa :: add(0, pos[0][i], 0);
    rep(i, 1, m) pos[1][i] = ++ spfa :: n, spfa :: add(0, pos[1][i], 0);
    rep(i, 1, n) rep(j, 1, m)
    {
        if((i + j) & 1)
        {
            spfa :: add(pos[0][i], pos[1][j], 1000000 - a[i][j]);
            spfa :: add(pos[1][j], pos[0][i], a[i][j]);
        }
        else
        {
            spfa :: add(pos[1][j], pos[0][i], 1000000 - a[i][j]);
            spfa :: add(pos[0][i], pos[1][j], a[i][j]);
        }
    }
}

signed main()
{
    t = read();
    while(t --)
    {
        n = read(), m = read();
        rep(i, 1, n - 1) rep(j, 1, m - 1) b[i][j] = read();
        build(), rebuild();
        if(!spfa :: work()) puts("NO");
        else
        {
            puts("YES");
            rep(i, 1, n) rep(j, 1, m)
            {
                if((i + j) & 1) a[i][j] += spfa :: dist[pos[1][j]] - spfa :: dist[pos[0][i]];
                else a[i][j] += spfa :: dist[pos[0][i]] - spfa :: dist[pos[1][j]];
                printf("%lld%c", a[i][j]," \n"[j == m]);
            }
        }
    }
    return 0;
}

/*

a_{i,j}

*/