\(\texttt{Introduction}\)

差分约束好题，感觉是 \(\texttt{day1}\) 质量最高的一道题。

\(\texttt{Solution}\)

为了研究方便，现将矩形定为 \(4\times 4\) 的，然后再进行拓展。

首先这道题有一个非常重要的结论，就是我们只要知道第一行以及第一列，我们就可以推出整个矩形，那么我们只是可以列出这么一个表格：

A	\(X_2\)	\(X_3\)	\(X_4\)
\(Y_2\)	B(1,1)-X(2)-Y(2)-A	B(1,2)-B(1,1)+Y(2)+A-X(3)	B(1,3)-B(1,2)+B(1,1)-Y(2)-A-X(4)
\(Y_3\)	B(2,1)-B(1,1)+X(2)+A-Y(3)	B(2,2)-B(2,1)-A+Y(3)-B(1,2)+B(1,1)+X(3)
\(Y_4\)

那么做到这里我们考虑将与 \(B\) 有关的全部设成常数，记作 \(C(i,j)\) 。

那么现在就是对于每一对 \((i,j)\) 存在下列不等式：

\[C(i,j)+A\times (-1)^{i+j-1}+X_i\times (-1)^{j-1}+Y_j\times (-1)^{i-1}\ge 0 \]

\[C(i,j)+A\times (-1)^{i+j-1}+X_i\times (-1)^{j-1}+Y_j\times (-1)^{i-1}\le 10^6 \]

\[0\le A \le 10^6 \]

那么如果不考虑 \(A\) 的话这道题就是一道模板的差分约束，但是我们现在要知道这个 \(A\) 的值，那么是否可以通过微调实现？

我们根据 \(C(i,j)\) 再列一个表格。

A	\(X_2\)	\(X_3\)	\(X_4\)
\(Y_2\)	C(2,2)-X(2)-Y(2)-A	C(2,3)+Y(2)+A-X(3)	C(2,4)-Y(2)-A-X(4)
\(Y_3\)	C(3,2)+X(2)+A-Y(3)	C(3,3)-A+Y(3)+X(3)	C(3,4)+A+X(4)-Y(3)
\(Y_4\)	C(4,2)-X(2)-A-Y(4)	C(4,3)-X(3)+A+Y(4)	C(4,4)-X(4)-A-Y(4)

那么我们考虑假设：

\[E(i)=A+X(i),i为偶数;E(i)=A-X(i),i为奇数 \]

\[F(i)=-Y(i),i为偶数;F(i)=Y(i),i为奇数 \]

\[E(i)-10^6 \le A \le E(i),E(i) \le A \le E(i)+10^6 \]

#include <bits/stdc++.h>
using namespace std;
inline long long read() {
	long long x=0,f=1;
	char ch=getchar();
	while ((!isdigit(ch))&&(ch!='-')) ch=getchar();
	if (ch=='-') f=-1,ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}
vector<pair<int,long long>> V[1010];
bool flag,vis[1010];
long long x,tag[1010],t,w,f1[10001010],Testing,n,m,i,j,cnt;
long long y,B[310][310],C[310][310],Answ[310][310],AA,dis[1010];
inline void add(int x,int y,int z) {
	V[x].push_back(make_pair(y,z));
}
int main() {
	//freopen("data.in","r",stdin);
	//freopen("TLE.out","w",stdout);
	Testing=read();
	for (; Testing; Testing--) {
		n=read();
		m=read();
		for (i=1; i<n; i++)for (j=1; j<m; j++) B[i][j]=read();
		for (i=2; i<=n; i++)
			for (j=2; j<=m; j++)
				C[i][j]=B[i-1][j-1]-C[i-1][j]-C[i][j-1]-C[i-1][j-1];
		
		//n+m-2个点
		for (i=2; i<=m; i++)
			for (j=2; j<=n; j++) {
				if (((i+j)&1)==0) {
					//0<=C(i,j)-E(i)+F(j)
					//E(i)-F(j)<=C(i,j)
					add(j+m,i,C[j][i]);
					//C(i,j)-E(i)+F(j)<=1000000
					//F(j)-E(i)<=1000000-C(i,j)
					add(i,j+m,1000000-C[j][i]);
				}
				if (((i+j)&1)==1) {
					//0<=C(i,j)+E(i)-F(j)<=1000000
					//F(j)-E(i)<=C(i,j)
					add(i,j+m,C[j][i]);
					add(j+m,i,1000000-C[j][i]);
				}
			}
		//E(i)>=0
		//E(0)-E(i)<=0
		//E(i)<=2000000
		//E(i)-E(0)<=2000000
		//E(i)+1000000>=0
		//E(i)>=-1000000
		//E(0)-E(i)<=1000000
		//E(i)<=1000000
		//E(i)-E(0)<=1000000
		//
		for (i=2; i<=m; i++)
			if (!(i&1)) {
				add(i,0,0);
				add(0,i,2000000);
			} else {
				add(i,0,1000000);
				add(0,i,1000000);
			}
		//E(0)-F(i)>=0
		//F(i)-E(0)<=0
		//F(i)-E(0)>=0
		//E(0)-F(i)<=0
		//-F(i)>=0
		//
		//-F(i)<=1000000
		//E(0)-F(i)<=1000000
		//F(i)<=1000000
		//F(i)-E(0)<=1000000
		//-F(i)>=0
		//F(i)-E(0)<=0
		for (i=2; i<=n; i++)
			if (!(i&1)) add(0,i+m,0),add(i+m,0,1000000);
			else add(i+m,0,0),add(0,i+m,1000000);
		for (i=2; i<=m; i++)
			for (j=i+1; j<=m; j++) {
				if ((!(i&1))&&(!(j&1))) {
					//E(i)-1000000<=E(j)
					//E(j)-1000000<=E(i)
					//E(i)-E(j)<=1000000,E(j)-E(i)<=1000000
					add(j,i,1000000);
					add(i,j,1000000);
				}
				if ((!(i&1))&&(j&1)) {
					//E(i)-1000000<=E(j)+1000000
					//E(i)-E(j)<=2000000
					//E(j)<=E(i)
					//E(j)-E(i)<=0
					add(j,i,2000000);
					add(i,j,0);
				}
				if ((i&1)&&(!(j&1))) {
					add(i,j,2000000);
					add(j,i,0);
				}
				if ((i&1)&&(j&1)) {
					//E(i)<=E(j)+1000000
					//E(j)<=E(i)+1000000
					//E
					add(j,i,1000000);
					add(i,j,1000000);

				}
			}
		for (i=0; i<=n+m+2; i++) dis[i]=1e18,tag[i]=0,vis[i]=false;
		t=1;
		w=1;
		dis[0]=0;
		f1[1]=0;
		flag=false;
		int sum = 0;
		while (t<=w) {
			if (flag) break;
			vis[f1[t]]=false;
			for (auto i:V[f1[t]])
			    {
				x=i.first;y=i.second;
				if (dis[x]>dis[f1[t]]+y) 
					{
						dis[x]=dis[f1[t]]+y;
						if ((tag[x]=tag[f1[t]]+1)>=n+m-1) {
							flag=true;
							break;
						}
						if (vis[x]==false) {
							w++;
							f1[w]=x;
							vis[x]=true;
						}
					}
				}
			t++;
		}
		for (i=0;i<=n+m+2;i++) V[i].clear();
		if (flag) puts("NO");
		else {
			puts("YES");
			AA=1e18;
			for (i=2; i<=m; i++)
				if (i % 2==0) AA=min(AA,dis[i]);
				else AA=min(AA,dis[i]+1000000);
		    AA=min(AA,(long long)1000000);
			Answ[1][1]=AA;
			for (i=2; i<=m; i++)
				if (i % 2==0)
					Answ[1][i]=dis[i]-AA;
				else Answ[1][i]=AA-dis[i];
			for (i=2; i<=n; i++)
				if (i % 2==1) Answ[i][1]=dis[i+m];
				else Answ[i][1]=-dis[i+m];
			for (i=2; i<=n; i++)
				for (j=2; j<=m; j++)
					Answ[i][j]=B[i-1][j-1]-Answ[i-1][j]-Answ[i-1][j-1]-Answ[i][j-1];
			for (i=1; i<=n; i++) {
				for (j=1; j<=m; j++)
				    {
					printf("%d ",Answ[i][j]);
				}
				puts("");
			}
		}
	}
	return 0;
}

被卡常了 /ll

woc,前向星竟然比不过邻接表。