正题
题目链接:https://www.luogu.com.cn/problem/P7515
题目大意
有一个(n*m)的矩形(A)，然后给出一个((n-1)*(m-1))的矩形(B)满足
[B_{i,j}=A_{i,j}+A_{i+1,j}+A_{i,j+1}+A_{i+1,j+1}
]
求能否构造合法矩形(A)使得(0leq a_{i,j}leq 10^6)
(1leq Tleq 10,1leq n,mleq 300,0leq b_{i,j}leq 4 imes 10^6)
解题思路
如果不考虑(a_{i,j})的限制显然很容易构造一个方案。
然后要考虑怎么调整到满足限制，不难发现我们每行/列进行(+1/-1/+1/-1...)操作不会改变(b)数组上的值，所以我们设(c_i)表示第(i)行进行了多少次，第(j)行进行了多少次，那么有
[0leq a_{i,j}±c_i±d_jleq 10^6
]
如果我们控制使得每个位置的(c_i)和(d_j)的符号不同那么就可以进行差分约束了。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const ll N=610;
struct node{
ll to,next,w;
}a[N*N];
ll T,n,m,b[N][N],c[N][N];
ll tot,cnt[N],ls[N],f[N];
bool v[N];deque<int> q;
void addl(ll x,ll y,ll w){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;a[tot].w=w;
return;
}
bool SPFA(){
memset(f,0x3f,sizeof(f));
memset(cnt,0,sizeof(cnt));
q.push_back(1);v[1]=cnt[1]=1;f[1]=0;
while(!q.empty()){
ll x=q.front();v[x]=0;q.pop_front();
for(ll i=ls[x];i;i=a[i].next){
ll y=a[i].to;
if(f[x]+a[i].w<f[y]){
f[y]=f[x]+a[i].w;
cnt[y]=cnt[x]+1;
if(cnt[y]>=n+m&&a[i].w<0)return 1;
if(!v[y]){
v[y]=1;
if(!q.empty()&&f[y]<f[q.front()])q.push_front(y);
else q.push_back(y);
}
}
}
}
return 0;
}
signed main()
{
scanf("%lld",&T);
while(T--){
memset(ls,0,sizeof(ls));tot=0;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<n;i++)
for(ll j=1;j<m;j++)
scanf("%lld",&b[i][j]);
memset(c,0,sizeof(c));
for(ll i=1;i<=m;i++)c[1][i]=0;
for(ll i=2;i<=n;i++){
c[i][1]=0;
for(ll j=2;j<=m;j++)
c[i][j]=b[i-1][j-1]-c[i-1][j-1]-c[i-1][j]-c[i][j-1];
}
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++){
if((i+j)&1)addl(i,j+n,c[i][j]),addl(j+n,i,1e6-c[i][j]);
else addl(j+n,i,c[i][j]),addl(i,j+n,1e6-c[i][j]);
}
if(!SPFA()){
puts("YES");
for(ll i=1;i<=n;i++,putchar('
'))
for(ll j=1;j<=m;j++){
if((i+j)&1)c[i][j]=c[i][j]+f[i]-f[j+n];
else c[i][j]=c[i][j]-f[i]+f[j+n];
printf("%lld ",c[i][j]);
}
}
else puts("NO");
}
return 0;
}