[cf1662J]Training Camp

对于一个元素，注意到其不合法当且仅当满足以下条件之一：

• 自身、同行比其小、同列比其大 的元素均未选
• 自身、同行比其大、同列比其小 的元素均未选

将同行同列值相邻的元素连边，每个条件中的元素即构成一条从\(1\)到\(n\)的链

另外，若某行/某列元素均未选，也会产生一条从\(1\)到\(n\)的链

换言之，不存在从\(1\)到\(n\)的链是合法的充分条件，而事实上也是必要的

反证法，假设合法但存在这样的链，考虑链上的第一个"拐点"：

不妨假设为行$\rightarrow $列，由于合法，列上必然选择一个比其大的元素

在此基础上，列上比其小的元素均未选，即可将行的部分转换到列上

根据结论，转化为最小割即可，为保证恰选择\(n\)个，可以将流量加上\(C>n\)

时间复杂度为\(O({\rm max\ flow}(n^{2},n^{2}))\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200;
int n,x,a[N][N],p[N];
int id(int x,int y){
	return (x-1)*n+y;
}
namespace Dinic{
	const int N=40000,M=60000;
	int S,T,E,head[N],Head[N],d[N];
	ll ans;queue<int>q;
	struct edge{
		int nex,to;ll len;
	}e[M<<1];
	void init(){
		E=0;
		memset(head,-1,sizeof(head));
	}
	void add(int x,int y,ll z){
		e[E]=edge{head[x],y,z},head[x]=E++;
		e[E]=edge{head[y],x,0},head[y]=E++;
	}
	bool bfs(){
		memset(d,-1,sizeof(d));
		d[S]=0,q.push(S);
		while (!q.empty()){
			int k=q.front();q.pop();
			for(int i=head[k];i!=-1;i=e[i].nex){
				int u=e[i].to;
				if ((e[i].len)&&(d[u]<0))d[u]=d[k]+1,q.push(u);
			}
		}
		return d[T]>=0;
	}
	ll dfs(int k,ll s){
		if (k==T)return s;
		ll ans=0;
		for(int &i=head[k];i!=-1;i=e[i].nex){
			int u=e[i].to;
			if ((e[i].len)&&(d[u]==d[k]+1)){
				ll p=dfs(u,min(s,(ll)e[i].len));
				e[i].len-=p,e[i^1].len+=p,s-=p,ans+=p;
				if (!s)return ans;
			}
		}
		return ans;
	}
	ll query(int s,int t){
		S=s,T=t,ans=0;
		memcpy(Head,head,sizeof(head));
		while (bfs()){
			ans+=dfs(S,1e18);
			memcpy(head,Head,sizeof(head));
		}
		return ans;
	}
};
int main(){
	scanf("%d",&n);
	Dinic::init();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
			if (a[i][j]==1)Dinic::add(0,id(i,j),1e18);
			if (a[i][j]==n)Dinic::add(id(i,j)+n*n,2*n*n+1,1e18);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			scanf("%d",&x);
			Dinic::add(id(i,j),id(i,j)+n*n,n+(x^1)+1);
		}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)p[a[i][j]]=j;
		for(int j=1;j<n;j++)Dinic::add(id(i,p[j])+n*n,id(i,p[j+1]),1e18);
	}
	for(int j=1;j<=n;j++){
		for(int i=1;i<=n;i++)p[a[i][j]]=i;
		for(int i=1;i<n;i++)Dinic::add(id(p[i],j)+n*n,id(p[i+1],j),1e18);
	}
	printf("%lld\n",n-(Dinic::query(0,2*n*n+1)-(ll)n*(n+1)));
	return 0;
}