这种数据范围和题目特点一眼网络流。
对于一种选法，我们考虑建立两个黑白矩阵，如果一个点 \((i,j)\) 被选，我们就将第 \(i\) 行中 \(a_{i,k}\le a_{i,j}\) 的 \((i,k)\) 在第一张网格图中染成黑色，将第 \(j\) 列中 \(a_{k,j}\le a_{i,j}\) 的点 \((k,j)\) 在第二张网格图中染成黑色，那么一种选择方法合法当且仅当两张图颜色完全相同。
考虑将“黑白”对应成与源汇的连接情况。将黑点看作与 \(S\) 相连，白点看成与 \(T\) 相连。然后考虑这样建模：
- \((S,(i,j),\infty)(a_{i,j}=1)\)
- \(((i,n+1),T,\infty),((n+1,i),T,\infty)\)。
- \(((i,rpos_{i,v+1}),(i,rpos_{i,v}),\infty),((cpos_{i,v+1},i),(cpos_{i,v},i),\infty)\)，其中 \(rpos_{i,v}\) 表示使得 \(a_{i,j}=v\) 的 \(j\)，\(cpos_{i,v}\) 表示使得 \(a_{j,i}=v\) 的 \(j\)，其中 \(rpos_{i,n+1}=cpos_{i,n+1}=n+1\)。
- \(((i,rpos_{i,v}),(i,rpos_{i,v+1}),1-c_{i,rpos_{i,v}})\)，割掉这条边表示第 \(i\) 行选择 \((i,rpos_{i,v})\)。
- \(((i,rpos_{i,a_{i,j}+1}),(cpos_{j,a_{i,j}+1},j),\infty),((cpos_{j,a_{i,j}+1},j),(i,rpos_{i,a_{i,j}+1}),\infty)\)。
然后 \(n\) 减最小割就是答案。
const int MAXN=128;
const int INF=0x3f3f3f3f;
int n,a[MAXN+5][MAXN+5],c[MAXN+5][MAXN+5];
int getid(int x,int y){return (x-1)*(n+1)+y;}
int posr[MAXN+5][MAXN+5],posc[MAXN+5][MAXN+5];
namespace MaxFlow{
const int MAXV=2e4;
const int MAXE=1e6;
int S=19999,T=20000,hd[MAXV+5],to[MAXE+5],cap[MAXE+5],nxt[MAXE+5],ec=1;
void adde(int u,int v,int f){
to[++ec]=v;cap[ec]=f;nxt[ec]=hd[u];hd[u]=ec;
to[++ec]=u;cap[ec]=0;nxt[ec]=hd[v];hd[v]=ec;
}
int dep[MAXV+5],now[MAXV+5];
bool getdep(){
memset(dep,-1,sizeof(dep));queue<int>q;q.push(S);dep[S]=0;
while(!q.empty()){
int x=q.front();q.pop();now[x]=hd[x];
for(int e=hd[x];e;e=nxt[e]){
int y=to[e],z=cap[e];
if(z&&!~dep[y])dep[y]=dep[x]+1,q.push(y);
}
}return ~dep[T];
}
int getflow(int x,int f){
if(x==T)return f;int ret=0;
for(int &e=now[x];e;e=nxt[e]){
int y=to[e],z=cap[e];
if(z&&dep[y]==dep[x]+1){
int w=getflow(y,min(f-ret,z));
cap[e]-=w;cap[e^1]+=w;ret+=w;
if(f==ret)return ret;
}
}return ret;
}
int dinic(){int ret=0;while(getdep())ret+=getflow(S,INF);return ret;}
}using namespace MaxFlow;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&c[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)posr[i][a[i][j]]=j,posc[j][a[i][j]]=i;
for(int i=1;i<=n;i++)posr[i][n+1]=posc[i][n+1]=n+1;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j]==1)adde(S,getid(i,j),INF);
for(int i=1;i<=n;i++)adde(getid(n+1,i),T,INF),adde(getid(i,n+1),T,INF);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
adde(getid(i,posr[i][j+1]),getid(i,posr[i][j]),INF);
adde(getid(posc[i][j+1],i),getid(posc[i][j],i),INF);
adde(getid(i,posr[i][j]),getid(i,posr[i][j+1]),c[i][posr[i][j]]^1);
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
adde(getid(i,posr[i][a[i][j]+1]),getid(posc[j][a[i][j]+1],j),INF);
adde(getid(posc[j][a[i][j]+1],j),getid(i,posr[i][a[i][j]+1]),INF);
}
printf("%d\n",n-dinic());
return 0;
}