洛谷传送门
DGMATRIX

分析

先任意构造出一个不一定满足值域的矩阵，现在只需要满足值域就可以了。

可以发现，给一行或一列依次加一减一2*2矩阵的和仍然不变，并且如果有解一定能构造出一组方案。

因为第一行和第一列如果确定，所以只要通过这样的加一减一，其它位置就能确定。

设行的选择为 \(dx[i]\)，列的选择为 \(dy[j]\)，那么就要满足 \(0\leq a[i][j]+dx[i]+dy[j]\leq 10^6\)

可是这样的加法好像也挺难做的，能不能强制让一个为加，一个为减，这是可行的，将矩阵黑白染色。

如果 \(i\) 和 \(j\) 奇偶性不同，那么 \(dy[j]-dx[i]\leq M-a[i][j],dx[i]-dy[j]\leq a[i][j]\)，

同奇同偶的情况正好将 \(dx[i]\) 和 \(dy[j]\) 调换即可，跑一遍最短路如果有负环那么无解，否则同样按照奇偶性输出方案即可。

代码(矩阵游戏)

#include 
#include 
#include 
#define rr register
using namespace std;
const int N=301,M=1000000; dequeq;
struct node{int y,w,next;}e[N*N<<1]; long long dis[N<<1];
int cnt[N<<1],et,as[N<<1],v[N<<1],a[N][N],n,m,flag;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
inline void add(int x,int y,int w){
	e[++et]=(node){y,w,as[x]},as[x]=et;
}
signed main(){
	for (rr int T=iut();T;--T){
		n=iut(),m=iut(),et=0;
		for (rr int i=1;i<=n+m;++i) dis[i]=1e15;
		for (rr int i=1;i<=n+m;++i) as[i]=cnt[i]=v[i]=0;
		for (rr int i=1;idis[x]+e[i].w){
				dis[e[i].y]=dis[x]+e[i].w;
				if (!v[e[i].y]){
					v[e[i].y]=1;
					if (!q.empty()&&dis[e[i].y]

#include 
#include 
#include 
using namespace std;
const int N=111,M=9; dequeq;
struct node{int y,w,next;}e[N*N<<1];
int et,as[N<<1],v[N<<1],dis[N<<1],a[N][N],n,m;
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
void add(int x,int y,int w){
	e[++et]=(node){y,w,as[x]},as[x]=et;
}
int main(){
	n=iut()+1;
	for (int i=1;i<=n*2;++i) dis[i]=0x3f3f3f3f;
	for (int i=1;idis[x]+e[i].w){
			dis[e[i].y]=dis[x]+e[i].w;
			if (!v[e[i].y]){
				v[e[i].y]=1;
				if (!q.empty()&&dis[e[i].y]