自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:00:41，当前版本为作者最后更新于2018-11-17 16:31:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

dls出的神题

考虑格子中填数对限制条件的影响。

每个格子填数只会对1行1列产生影响。

所以把行限制、列限制分别作为点，格子为边，就有了一张二分图。

我们需要限定权值，使得每个点的点权恰等于它所有边的边权的异或和。

考虑求出一棵生成树，剩下的边先设其全为0。

显然，每条边的权可以一遍dfs推出来。再判断下合法性、有无相同即可。

对于非树边，我们可以随机给定一个权值，然后修改一下点权，再dfs即可（随机出来如果相同的话窝也没办法了QAQ）。

还有一种情况：填的格子可能没有行限制或没有列限制。

那先随机给一个权值，然后再跑。最后如果答案不合法，可以修改一个只有一个限制的格子填的数来使答案合法。

代码巨丑，时间复杂度$O(Tn^3)$，可以写得更优的QAQ。

Code：

#include<cstdio>
#include<cctype>
#include<utility>
#include<unordered_set>
#include<cstring>
#define N 500
#define LoveLive unsigned long long
const LoveLive lim=(1uLL<<60)-1;
struct istream{
	template<typename T>
		inline istream&operator>>(T&d){
			static int c;
			while(!isdigit(c=getchar()));
			for(d=0;isdigit(c);c=getchar())
				d=(d<<3)+(d<<1)+(c^'0');
			return*this;
		}
}cin;
int T_,n,m,kind[N][N];
int cc,cnt,fa[N*N];
int g[N][N];
LoveLive dis[N*N],r[N*N],dot[N*N],V[N*N];
std::pair<int,int>pr[N][N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct edge{
	int u,v;
	bool b;
}e[N*N];
struct random{
	LoveLive seed;
	inline void srand(LoveLive s){
		seed=s;
	}
	inline LoveLive operator()(){return(((seed*=37)+=7)*=19260817)^=31;}
}Rand;
#define rand Rand
struct Tree{
	struct EDGE{
		int to,nxt,id;
	}e[N*N<<2];
	int cnt,head[N*N<<1];
	inline void init(){
		memset(head,0,sizeof head);
		cnt=0;
	}
	inline void addedge(int u,int v,int id){
		e[++cnt]=(EDGE){v,head[u],id};
		head[u]=cnt;
		e[++cnt]=(EDGE){u,head[v],id};
		head[v]=cnt;
	}
	void dfs(int now,int pre){
		for(int i=head[now];i;i=e[i].nxt)
		if(e[i].to!=pre){
			dfs(e[i].to,now);
			dis[e[i].id]=r[e[i].to]^dot[e[i].to];
			dot[now]^=dis[e[i].id];
		}
	}
}T;
int main(){
	rand.srand(79877863023177851LL);
	for(cin>>T_;T_--;){
		cin>>n>>m;
		memset(kind,0,sizeof kind);
		memset(g,0,sizeof g);
		memset(dot,0,sizeof dot);
		memset(dis,0,sizeof dis);
		T.init();
		for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		cin>>kind[i][j];
		cc=0;
		for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			pr[i][j]=std::make_pair(0,0);
			if(kind[i][j]==1||kind[i][j]==3)cin>>r[pr[i][j].first=++cc];
			if(kind[i][j]==2||kind[i][j]==3)cin>>r[pr[i][j].second=++cc];
		}
		cnt=0;
		for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		if(kind[i][j]==4){
			if(pr[i-1][j].first&&!pr[i][j].first)pr[i][j].first=pr[i-1][j].first;
			if(pr[i][j-1].second&&!pr[i][j].second)pr[i][j].second=pr[i][j-1].second;
		}
		for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		if(kind[i][j]==4){
			e[g[i][j]=++cnt]=(edge){pr[i][j].first,pr[i][j].second,0};
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j)
			if(kind[i][j]==4){
				if(pr[i][j].first==0||pr[i][j].second==0){
					e[g[i][j]].b=1;
					dis[g[i][j]]=rand()%lim+1;
				}
				if(!pr[i][j].first&&pr[i][j].second){
					dot[pr[i][j].second]^=dis[g[i][j]];
				}else
				if(pr[i][j].first&&!pr[i][j].second){
					dot[pr[i][j].first]^=dis[g[i][j]];
				}
			}
		}
		for(int i=1;i<=cc;++i)fa[i]=i;
		for(int i=1;i<=cnt;++i)
		if(e[i].u&&e[i].v&&find(e[i].u)!=find(e[i].v)){
			T.addedge(e[i].u,e[i].v,i);
			fa[find(e[i].v)]=e[i].u;
			e[i].b=1;
		}
		for(int i=1;i<=cnt;++i)if(!e[i].b){
			dis[i]=rand()%lim+1;
			dot[e[i].u]^=dis[i];
			dot[e[i].v]^=dis[i];
		}
		T.dfs(1,1);
		bool ok=1;
		memset(V,0,sizeof V);
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j)
			if(kind[i][j]==4){
				if(pr[i][j].first)V[pr[i][j].first]^=dis[g[i][j]];
				if(pr[i][j].second)V[pr[i][j].second]^=dis[g[i][j]];
			}
		}
		for(int x=1;x<=cc&&ok;++x)
		if(V[x]!=r[x]){
			bool yes=0;
			for(int i=1;i<=n&&!yes;++i){
				for(int j=1;j<=m&&!yes;++j)
				if(kind[i][j]==4)
				if(pr[i][j].first==x&&!pr[i][j].second||pr[i][j].second==x&&!pr[i][j].first){
					dis[g[i][j]]^=V[x]^r[x];
					yes=1;
				}
			}
			ok&=yes;
		}
		static std::unordered_set<LoveLive>st;
		st.clear();
		for(int i=1;i<=cnt&&ok;++i)
		if(!dis[i]||st.count(dis[i]))ok=0;else st.insert(dis[i]);
		if(ok){
			for(int i=1;i<=n;++i){
				for(int j=1;j<=m;++j)if(g[i][j])printf("%llu ",dis[g[i][j]]);
				putchar('\n');
			}
		}else puts("-1");
	}
	return 0;
}