P7515 [省选联考 2021 A 卷] 矩阵游戏
大意
给出 \(b_{i, j} = a_{i - 1, j} + a_{i, j - 1} + a_{i - 1, j - 1} + a_{i, j}\)，要求给出一组 \(a\) 的可行解，保证 \(0 \le a_{i, j} \le 10 ^ 6\)。
思路
这集真的神了。
我们想一个问题，首先这个题我们很容易构造出一个 \(a\)，使其满足 \(b\) 的性质，我们将 \(a_{i, 1}\) 和 \(a_{1, i}\) 都设为 \(0\)，那么我们有这样的转移式子：\(a_{i, j} = b_{i - 1, j - 1} - a_{i - 1, j} - a_{i, j - 1} - a_{i - 1, j - 1}\)，这样构造出来的 \(a\) 是含有负数的，但是我们考虑进行调整。
这里有一个小巧思，我们考虑对于每一行和每一列进行增量的操作，加减交替，这样会得到以下这个样子的矩阵：
\[\begin{pmatrix}
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{pmatrix}\]
有什么用呢？？？我们发现 \((r_1 + c_1) + (-r_1 + c_2) + (r_2 - c_1) + (-r_2 - c_2) = 0\)，那么这样我们就在不改变 \(b\) 的情况下可以对 \(a\) 进行调整，那么会变成类似于这样的差分约束系统：\(0 \le a_{i, j} \pm r_i \pm c_i \le 10 ^ 6\)，我们就直接对这样的建立差分约束系统，然后跑 SPFA 即可（注意判负环，如果有负环说明就没有答案）
代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std;const int MAXN = 1005;
const int INF = 1000000;
int T;
int n, m;
int b[MAXN][MAXN];
int a[MAXN][MAXN];
vector<pair<int, int> > g[MAXN];
bool vis[MAXN << 1];
int dis[MAXN << 1], in[MAXN << 1];
queue<int> q;void init(){while(!q.empty()) q.pop();for(int i = 1;i <= n + m;i ++){dis[i] = 0;vis[i] = 1;in[i] = 0;q.push(i);}
}void solve(){cin >> n >> m;for(int i = 1;i < n;i ++){for(int j = 1;j < m;j ++){cin >> 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];
// cout << a[i][j] << ' ';}
// cout << endl;}for(int i = 1;i <= n + m + 1;i ++) g[i].clear();for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){if((i + j) & 1){g[i].push_back(make_pair(j + n, a[i][j]));g[j + n].push_back(make_pair(i, INF - a[i][j]));}else{g[j + n].push_back(make_pair(i, a[i][j]));g[i].push_back(make_pair(j + n, INF - a[i][j]));}}}init();while(!q.empty()){int u = q.front(); q.pop(); vis[u] = 0;for(auto x : g[u]){int v = x.first, w = x.second;if(dis[u] + w < dis[v]){dis[v] = dis[u] + w;if(!vis[v]){in[v] ++;if(in[v] > n + m + 1){cout << "NO\n";return;}vis[v] = 1;q.push(v);}}}}bool flag = 1;
// cout << "YES\n";for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){if((i + j) & 1) a[i][j] += (dis[i] - dis[j + n]);else a[i][j] += (dis[j + n] - dis[i]);if(a[i][j] < 0) flag = 0;
// cout << a[i][j] << ' ';}
// cout << '\n';}if(flag){cout << "YES\n";for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){cout << a[i][j] << ' ';}cout << '\n';}}else cout << "NO\n";
}int main(){// freopen("matrix.in", "r", stdin);// freopen("matrix.out", "w", stdout);cin.tie(0) -> ios::sync_with_stdio(0);cin >> T;while(T --){solve();}return 0;
}