- 给出一个((n-1) imes(m-1))的矩阵(b)满足(b_{i,j}=a_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1})，要求构造一个(n imes m)的矩阵(a)满足所有数都在([0,10^6])范围内。
- 数据组数(le10)，(n,mle300)
不论值域的随意构造
先不管([0,10^6])这个值域限制，想要构造一组答案还是很简单的。
我们不妨让最后一行和最后一列的数都为(0)，然后从右下角开始枚举，则枚举到每个位置时它右方、下方、右下方的位置上的值都已经确定了，那么这个位置上的值也自然就确定了。
差分约束
考虑如果给某一行或某一列交错(pm1)是不会影响和的。
我们给奇数行交错(mp1)，给偶数行交错(pm1)；给奇数列交错(pm1)，给偶数列交错(mp1)。
发现就相当于要满足：
[0le a_{i,j}+egin{cases}X_i-Y_j&i+j exttt{ is odd},\Y_j-X_i&i+j exttt{ is even}end{cases}le 10^6
]
相当于对于每个位置都可以列出两个差分约束的方程。
经典差分约束建图之后，跑遍(SPFA)即可（如果存在负环说明无解）。
代码：(O(Tnm(n+m)))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 300
#define add(x,y,z) (G[x].push_back(make_pair(y,z)))
using namespace std;
int n,m,a[N+5][N+5],b[N+5][N+5];vector<pair<int,int> > G[2*N+5];vector<pair<int,int> >::iterator it;
int ct[2*N+5],IQ[2*N+5];long long dis[2*N+5];queue<int> q;I bool SPFA()//SPFA
{
RI i,k,y;for(i=1;i<=n+m;++i) ct[i]=dis[i]=0,IQ[i]=1,q.push(i);W(!q.empty())
{
if(IQ[k=q.front()]=0,q.pop(),++ct[k]>n+m+1) {W(!q.empty()) q.pop();return 0;}//判负环
for(it=G[k].begin();it!=G[k].end();++it)
dis[k]+it->second<dis[y=it->first]&&(dis[y]=dis[k]+it->second,!IQ[y]&&(q.push(y),IQ[y]=1));
}return 1;
}
int main()
{
RI Tt,i,j;scanf("%d",&Tt);W(Tt--)
{
for(scanf("%d%d",&n,&m),i=1;i<=n+m;++i) G[i].clear();//清空图
for(i=1;i^n;++i) for(j=1;j^m;++j) scanf("%d",&b[i][j]);
for(i=n;i;--i) for(j=m;j;--j) a[i][j]=i==n||j==m?0:b[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1],//随意构造
(i^j)&1?(add(i,n+j,a[i][j]),add(n+j,i,1e6-a[i][j])):(add(n+j,i,a[i][j]),add(i,n+j,1e6-a[i][j]));//列出两个差分方程建图
if(!SPFA()) {puts("NO");continue;}puts("YES");
for(i=1;i<=n;++i) for(j=1;j<=m;++j) printf("%d%c",a[i][j]+((i^j)&1?1:-1)*(dis[i]-dis[n+j]),"
"[j==m]);//输出答案
}return 0;
}