差分约束

解决形如 $a_i \le x_i - y_i \le b_i$ 的不等式组，其中 $a_i,b_i$ 是给定的常数。

我们尝试连接边通过 $\operatorname{spfa}$ 解决。
连接以下两条边，跑最短路。
$$\Large{x_i \overset{-a_i}{\to} y_i}$$
$$\Large{y_i \overset{b_i}{\to} x_i}$$

例题：
[P7515](https://www.luogu.com.cn/problem/P7515)

Alice 有一个 $n \times m$ 的矩阵 $a_{i, j}$（$1 \le i \le n$，$1 \le j \le m$），其每个元素为大小不超过 ${10}^6$ 的非负整数。

Bob 根据该矩阵生成了一个 $(n - 1) \times (m - 1)$ 的矩阵 $b_{i, j}$（$1 \le i \le n - 1$，$1 \le j \le m - 1$），每个元素的生成公式为

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

现在 Alice 忘记了矩阵 $a_{i, j}$，请你根据 Bob 给出的矩阵 $b_{i, j}$ 还原出 $a_{i, j}$。



数据：$1 \le T \le 10$，$2 \le n, m \le 300$，$0 \le b_{i, j} \le 4 \times {10}^6$。

如果没有数据范围的限制，我们直接令 $a_{1\sim n,m},a_{n,{1 \sim m}}$ 都为 $0$，直接反解。

考虑调整 $a$ 直到合法或者输出无解。

因为 $ b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1} $，所以只要贴着的四个和不变就可以。

考虑加减构造，每行 $+r_i,-r_i,+r_i,-r_i \ \cdots$，
每列 $+c_i,-c_i,+c_i,-c_i \ \cdots$  

然后会出现形如 $x+y,x-y$ 的限制。

我们再根据奇偶性调整符号符合 $x-y$，套上差分约束就行了。

  1 #include<bits/stdc++.h>
  2 
  3 const int N=3e2+20;
  4 const int inf=1e6;
  5 using namespace std;
  6 
  7 struct edge{
  8   int next,to,w;
  9 }e[N*N<<1];
 10 int head[N<<1],cnt;
 11 void add(int f,int t,int w){
 12   e[++cnt]=edge{head[f],t,w},head[f]=cnt;
 13 }
 14 
 15 int T,n,m;
 16 int a[N][N],b[N][N];
 17 int dis[N<<1],s,len,d[N<<1],vis[N<<1];
 18 
 19 bool spfa(int s){
 20   memset(dis,0x3f,sizeof dis);
 21   memset(vis,0,sizeof vis);
 22   memset(d,0,sizeof d);
 23   queue<int>Q;
 24   dis[s]=0;
 25   Q.push(s);
 26   while(Q.size()){
 27     int u=Q.front();
 28     Q.pop();
 29     vis[u]=0;
 30     for(int i=head[u];i;i=e[i].next){
 31       int v=e[i].to;
 32       if(dis[v]>dis[u]+e[i].w){
 33         dis[v]=dis[u]+e[i].w;
 34         if(++d[v]>n+m)return 0;
 35         if(!vis[v]) Q.push(v);
 36         vis[v] = 1;
 37       }
 38     }
 39   }
 40   return 1;
 41 }
 42 
 43 void solve(){
 44   cin >> n >> m;
 45   len = n + m; cnt = 0;
 46   for(int i=1;i<=n+m+2;++i)head[i]=0;
 47   for(int i=1;i<n;++i){
 48     for(int j=1;j<m;++j){
 49       cin>>b[i][j];
 50     }
 51   }
 52   memset(a,0,sizeof a);
 53   for(int i=n-1;i>=1;--i)
 54   for(int j=m-1;j>=1;--j){
 55     a[i][j]=b[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1];
 56   }
 57   for(int i=1;i<=n;++i){
 58     for(int j=1;j<=m;++j){
 59       if(!((i + j) & 1)) {
 60         add(i,n+j,a[i][j]);
 61         add(n+j,i,inf-a[i][j]);
 62       }  else {
 63         add(n+j,i,a[i][j]);
 64         add(i,n+j,inf-a[i][j]);
 65       }
 66     }
 67   }
 68   int tag = spfa(1);
 69   if(!tag) {
 70     cout << "NO\n";
 71     return;
 72   }
 73   for(int i=1;i<=n;++i){
 74     for(int j=1;j<=m;++j){
 75       if(!((i + j) & 1)) {
 76         a[i][j] += dis[i] - dis[n+j];
 77         if(a[i][j] < 0 || a[i][j] > inf) {cout << "NO\n"; return;}
 78       } else {
 79         a[i][j] += - dis[i] + dis[n+j];
 80         if(a[i][j] < 0 || a[i][j] > inf) {cout << "NO\n"; return;}
 81       }
 82     }
 83   }
 84   cout << "YES\n";
 85   for(int i=1;i<=n;++i){
 86     for(int j=1;j<=m;++j)
 87         cout << a[i][j] << " ";
 88     cout << endl;
 89   }
 90 }
 91 
 92 
 93 int main(){
 94 
 95   cin >> T;
 96   while(T--){
 97     solve();
 98   }
 99   return 0;
100 }