无内鬼，想整活。看到 cf 上有人写 2-SAT

然后赛后去写 2-SAT 整活。然后WA了。

2-SAT 部分从模板复制来的，感觉问题出在建图。

完整代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int Maxn=4e4+5;
const int Maxm=1e6+5;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
struct edge{
	int u,v,nx;
}p[Maxm<<1];
int n,m,ne,f[Maxn],a[105][105];
int top,sta[Maxn];bool vis[Maxn];
int dfn[Maxn],low[Maxn],cnt,arr[Maxn],sum;
int id(int x,int y){return (x-1)*m+y;}
void read(int u,int v)
{	p[++ne].v=v;
	p[ne].u=u;
	p[ne].nx=f[u];
	f[u]=ne;
	printf("u,v:%d %d\n",u,v);
}
void Tarjan(int x)
{	low[x]=dfn[x]=++cnt;
	sta[++top]=x;vis[x]=1;
	for(int k=f[x];k;k=p[k].nx)
	{	int v=p[k].v;
		if(!dfn[v])
		{	Tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(vis[v])
			low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x])
	{	sum++;
		while(sta[top]!=x)
		{	arr[sta[top]]=sum;
			vis[sta[top]]=0;
			top--;
		}
		arr[sta[top]]=sum;
		vis[sta[top]]=0;
		top--;
	}
}
int main()
{	int T;
	scanf("%d",&T);
	while(T--)
	{	ne=0;top=0;sum=0;cnt=0;
		memset(f,0,sizeof(f));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=n*m*2;i++)
			dfn[i]=low[i]=arr[i]=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				for(int k=0;k<4;k++)
				{	int x=i+dx[k],y=j+dy[k];
					if(x<1||y<1||x>n||y>m)continue;
					if(a[i][j]==a[x][y])
					{	read(id(i,j),id(x,y)+n*m);
						read(id(i,j)+n*m,id(x,y));
					}
					if(a[i][j]==a[x][y]+1)
					{	read(id(i,j)+n*m,id(x,y));
						read(id(i,j),id(x,y));
						read(id(i,j)+n*m,id(x,y)+n*m);
					}
					if(a[i][j]+1==a[x][y])
					{	read(id(i,j)+n*m,id(x,y)+n*m);
						read(id(i,j),id(x,y));
						read(id(i,j),id(x,y)+n*m);
					}
				}
		for(int i=1;i<=2*n*m;i++)
			if(!dfn[i])Tarjan(i);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(arr[id(i,j)]>arr[id(i,j)+n*m])a[i][j]++;
		for(int i=1;i<=n*m;i++)
			printf("%d %d\n",arr[i],arr[i+n*m]);
		for(int i=1;i<=n;i++)
		{	for(int j=1;j<=m;j++)
				printf("%d ",a[i][j]);
			printf("\n");
		} 
	}
	return 0;
}

建图部分考虑了 $2$ 种：

第一个 $\texttt{WA on 2}$ ：

for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		for(int k=0;k<4;k++)
		{	int x=i+dx[k],y=j+dy[k];
			if(x<1||y<1||x>n||y>m)continue;
			if(a[i][j]==a[x][y])
			{	read(id(i,j),id(x,y)+n*m);
				read(id(i,j)+n*m,id(x,y));
			}
			if(a[i][j]==a[x][y]+1)
			{	read(id(i,j)+n*m,id(x,y));
				read(id(i,j),id(x,y));
				read(id(i,j)+n*m,id(x,y)+n*m);
			}
		}

第一个 $\texttt{WA on 1}$ （其实就是样例的最后一个数据）：

for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				for(int k=0;k<4;k++)
				{	int x=i+dx[k],y=j+dy[k];
					if(x<1||y<1||x>n||y>m)continue;
					if(a[i][j]==a[x][y])
					{	read(id(i,j),id(x,y)+n*m);
						read(id(i,j)+n*m,id(x,y));
					}
					if(a[i][j]==a[x][y]+1)
					{	read(id(i,j)+n*m,id(x,y));
						read(id(i,j),id(x,y));
						read(id(i,j)+n*m,id(x,y)+n*m);
					}
					if(a[i][j]+1==a[x][y])
					{	read(id(i,j)+n*m,id(x,y)+n*m);
						read(id(i,j),id(x,y));
						read(id(i,j),id(x,y)+n*m);
					}
				}