题解 P4487 【[BJWC2018]Cross sum】
dls出的神题
考虑格子中填数对限制条件的影响。
每个格子填数只会对1行1列产生影响。
所以把行限制、列限制分别作为点，格子为边，就有了一张二分图。
我们需要限定权值，使得每个点的点权恰等于它所有边的边权的异或和。
考虑求出一棵生成树，剩下的边先设其全为0。
显然，每条边的权可以一遍dfs推出来。再判断下合法性、有无相同即可。
对于非树边，我们可以随机给定一个权值，然后修改一下点权，再dfs即可（随机出来如果相同的话窝也没办法了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;
}