BZOJ4205: 卡牌配对
Aug 18, 2015 08:39:03 PM
题解:
首先暴力连边匹配肯定是不行的...
由于$200$以内的质数仅有$46$个,我们构造三类点$ab(p_1,p_2),ac(p_1,p_2),bc(p_1,p_2)$分别表示参数1能被$p_1$整除,参数2能被$p_2$整除,剩下的依此类推.
然后对于左侧的点向符合条件的中间点连边.
对于右侧的点从符合条件的中间点连边.
这样做事实上是边分组,很显然是正确的.
直接用dinic玩就行了.
代码:
#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
struct Solver{
static const int V=100010;
static const int E=3000010;
int head[V],next[E],flow[E],end[E],ind,d[V];
inline void reset(){
memset(head,-1,sizeof head);
ind=0;
}
inline void addedge(int a,int b,int f){
int q=ind++;
end[q]=b;
next[q]=head[a];
head[a]=q;
flow[q]=f;
}
inline void make(int a,int b,int f){
addedge(a,b,f);
addedge(b,a,0);
}
inline bool bfs(int s,int t){
static int q[V];
int fr=0,ta=0;
memset(d,-1,sizeof d);
d[q[ta++]=s]=0;
while(fr!=ta){
int i=q[fr++];
for(int j=head[i];j!=-1;j=next[j])
if(flow[j]&&d[end[j]]==-1)
d[q[ta++]=end[j]]=d[i]+1;
}
return d[t]!=-1;
}
inline int dinic(int p,int t,int Maxflow){
if(p==t)
return Maxflow;
int last=Maxflow;
for(int j=head[p];j!=-1;j=next[j])
if(flow[j]&&d[end[j]]==d[p]+1){
int to=dinic(end[j],t,flow[j]>last?last:flow[j]);
if(to){
flow[j]-=to;
flow[j^1]+=to;
if(!(last-=to))
return Maxflow;
}
}
d[p]=-1;
return Maxflow-last;
}
inline int Maxflow(int s,int t){
int re=0;
while(bfs(s,t))
re+=dinic(s,t,inf);
return re;
}
}g;
#define N 210
int p[N],cnt;
bool np[N];
inline void pre(){
int i,j;
for(i=2;i<=200;++i){
if(!np[i])
p[++cnt]=i;
for(j=1;j<=cnt&&p[j]*i<=200;++j){
np[i*p[j]]=1;
if(i%p[j]==0)
break;
}
}
}
int a[51][51],b[51][51],c[51][51];
int x[2][30010],y[2][30010],z[2][30010];
vector<int>v[N];
int main(){
pre();
int n,m;
cin>>n>>m;
int i,j,k;
for(i=1;i<=n;++i)
scanf("%d%d%d",&x[0][i],&y[0][i],&z[0][i]);
for(i=1;i<=m;++i)
scanf("%d%d%d",&x[1][i],&y[1][i],&z[1][i]);
for(i=1;i<=200;++i)
for(j=1;j<=cnt;++j)
if(i%p[j]==0)
v[i].push_back(j);
int id=n+m;
for(i=1;i<=cnt;++i)
for(j=1;j<=cnt;++j){
a[i][j]=++id;
b[i][j]=++id;
c[i][j]=++id;
}
int s=0,t=++id;
g.reset();
for(i=1;i<=n;++i)
g.make(s,i,1);
for(i=1;i<=m;++i)
g.make(n+i,t,1);
int p,q;
for(i=1;i<=n;++i){
for(j=0;j<v[x[0][i]].size();++j)
for(k=0;k<v[y[0][i]].size();++k){
p=v[x[0][i]][j];
q=v[y[0][i]][k];
g.make(i,a[p][q],1);
}
for(j=0;j<v[x[0][i]].size();++j)
for(k=0;k<v[z[0][i]].size();++k){
p=v[x[0][i]][j];
q=v[z[0][i]][k];
g.make(i,b[p][q],1);
}
for(j=0;j<v[y[0][i]].size();++j)
for(k=0;k<v[z[0][i]].size();++k){
p=v[y[0][i]][j];
q=v[z[0][i]][k];
g.make(i,c[p][q],1);
}
}
for(i=1;i<=m;++i){
for(j=0;j<v[x[1][i]].size();++j)
for(k=0;k<v[y[1][i]].size();++k){
p=v[x[1][i]][j];
q=v[y[1][i]][k];
g.make(a[p][q],n+i,1);
}
for(j=0;j<v[x[1][i]].size();++j)
for(k=0;k<v[z[1][i]].size();++k){
p=v[x[1][i]][j];
q=v[z[1][i]][k];
g.make(b[p][q],n+i,1);
}
for(j=0;j<v[y[1][i]].size();++j)
for(k=0;k<v[z[1][i]].size();++k){
p=v[y[1][i]][j];
q=v[z[1][i]][k];
g.make(c[p][q],n+i,1);
}
}
cout<<g.Maxflow(s,t)<<endl;
return 0;
}
BZOJ1443: [JSOI2009]游戏Game 二分图+博弈论+网络流
Mar 06, 2015 02:08:04 PM
思路:
首先将图黑白二染色变成二分图.
然后求出一组最大匹配.
如果某个点不在匹配中,那么先手选择这个点.
那么后手只能走向一个匹配点(否则就不是最大匹配了).于是先手就可以沿着匹配边走回来.
那么此时如果后手还能走的话,就必定走到一个匹配点上.(否则就存在增广路了).于是先手又沿着匹配边走回来.
最后总是后手无路可走.因此先手必胜.
因此如果某个点不是最大匹配的必须点.就可以选择这个点.
如何找出这个呢?
在残量网络上,从\(S\)出发能够遍历到的左端的点,以及从\(T\)出发能够反向遍历到的右端的点.
证明的话,就是如果能够遍历到,就证明可以被换掉,而使得匹配数不减少.(稍微脑补一下)
(注意总点数要开2W,我不知道为什么)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF ~0U>>1
struct Solver{
static const int V=20010;
static const int E=V<<2;
int head[V],next[E],end[E],flow[E],ind;
int gap[V],d[V],stk[V],top,cur[V];
inline void reset(){
ind=top=0,memset(head,-1,sizeof head);
}
inline void addedge(int a,int b,int f){
int q=ind++;
end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
}
inline void make(int a,int b,int f){
//printf("%d %d %d\n",a,b,f);
addedge(a,b,f),addedge(b,a,0);
}
inline void bfs(int T){
static int q[V];
int fr=0,ta=0;
memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
while(fr^ta){
int i=q[fr++];
for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
}
}
inline int Maxflow(int S,int T){
int re=0,ins,Min,i,u=S;
bfs(T),memcpy(cur,head,sizeof cur);
while(d[S]<T-S+1){
if(u==T){
for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
u=end[stk[top=ins]^1];
}
if(u!=T&&!gap[d[u]-1])break;
bool find=0;
for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
find=1,ins=j;break;
}
if(find){
stk[top++]=cur[u]=ins,u=end[ins];
}
else{
Min=T-S+1;
for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
cur[u]=j,Min=d[end[j]];
if(!--gap[d[u]])break;
++gap[d[u]=Min+1];
if(u!=S)u=end[stk[--top]^1];
}
}
return re;
}
}Stg;
#define N 110
char s[N];
int lab[N][N],x[N*N],y[N*N];
int res[N*N],nums;
bool vis[N*N];
inline void bfs(int S,bool rev){
static int q[N*N];
int fr=0,ta=0;
memset(vis,0,sizeof vis),vis[S]=1,q[ta++]=S;
while(fr^ta){
int i=q[fr++];
for(int j=Stg.head[i];j!=-1;j=Stg.next[j])if(Stg.flow[j^rev]&&!vis[Stg.end[j]])
vis[Stg.end[j]]=1,q[ta++]=Stg.end[j];
}
}
int main(){
int n,m;scanf("%d%d",&n,&m);
register int i,j;
int cnt=0;
for(i=1;i<=n;++i){
scanf("%s",s+1);
for(j=1;j<=m;++j)if(s[j]!='#')lab[i][j]=++cnt,x[cnt]=i,y[cnt]=j;
}
int S=0,T=cnt+1,num0=0,num1=0;
Stg.reset();
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]){
if((i+j)&1){
++num1;
Stg.make(S,lab[i][j],1);
if(lab[i-1][j])Stg.make(lab[i][j],lab[i-1][j],INF);
if(lab[i+1][j])Stg.make(lab[i][j],lab[i+1][j],INF);
if(lab[i][j-1])Stg.make(lab[i][j],lab[i][j-1],INF);
if(lab[i][j+1])Stg.make(lab[i][j],lab[i][j+1],INF);
}
else
++num0,Stg.make(lab[i][j],T,1);
}
if(num0==0&&num1==0){
puts("LOSE");
return 0;
}
int re=Stg.Maxflow(S,T);
/*for(i=S;i<=T;++i)for(j=Stg.head[i];j!=-1;j=Stg.next[j])
printf("%d %d %d\n",i,Stg.end[j],Stg.flow[j]);*/
if(num0==num1&&re==num0){
puts("LOSE");
return 0;
}
puts("WIN");
bfs(S,0);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)&1)&&vis[lab[i][j]])res[++nums]=lab[i][j];
bfs(T,1);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)%2==0)&&vis[lab[i][j]])res[++nums]=lab[i][j];
sort(res+1,res+nums+1);
for(i=1;i<=nums;++i){
printf("%d %d\n",x[res[i]],y[res[i]]);
}
return 0;
}
BZOJ1570:[JSOI2008]Blue Mary的旅行 暴力+网络流
Mar 06, 2015 02:05:50 PM
思路:
暴力枚举答案,然后将点分层,边总是从该层连向下一层.
然后判断最大流是不是满足题意.
具体连边看代码.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF ~0U>>1
struct Solver{
static const int V=50*100;
static const int E=2450*100*2;
int head[V],next[E],end[E],flow[E],ind;
int d[V],gap[V],stk[V],top,cur[V];
inline void reset(){
ind=top=0,memset(head,-1,sizeof head);
}
inline void addedge(int a,int b,int f){
int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
}
inline void make(int a,int b,int f){
/*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);
}
inline void bfs(int T){
static int q[V];int fr=0,ta=0;
memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
while(fr^ta){
int i=q[fr++];
for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
}
}
inline int Maxflow(int S,int T){
bfs(T),memcpy(cur,head,sizeof cur);
int re=0,Min,ins,i,u=S;
while(d[S]<T-S+1){
if(u==T){
for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])ins=i,Min=flow[stk[i]];
for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
u=end[stk[top=ins]^1];
}
if(u!=T&&!gap[d[u]-1])break;
bool find=0;
for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
find=1,ins=j;break;
}
if(find){stk[top++]=cur[u]=ins,u=end[ins];}
else{
Min=T-S+1;
for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
cur[u]=j,Min=d[end[j]];
if(!--gap[d[u]])break;
++gap[d[u]=Min+1];
if(u!=S)u=end[stk[--top]^1];
}
}
return re;
}
}Stg;
struct Edge{
int u,v,f;
}E[2510];
#define get(x,dep) ((dep-1)*n+x)
int main(){
int n,m,T;scanf("%d%d%d",&n,&m,&T);
register int i,j;
for(i=1;i<=m;++i)scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].f);
int re;
for(re=1;;++re){
Stg.reset();
for(i=1;i<=m;++i)for(j=1;j<=re;++j)Stg.make(get(E[i].u,j),get(E[i].v,j+1),E[i].f);
for(j=1;j<=re;++j)Stg.make(0,get(1,j),INF);
for(j=2;j<=re+1;++j)Stg.make(get(n,j),n*(re+1)+1,INF);
int now=Stg.Maxflow(0,n*(re+1)+1);
//printf("%d\n",now);
if(now>=T)break;
}
printf("%d\n",re);
return 0;
}
BZOJ1189:[HNOI2007]紧急疏散evacuate 二分+最大流
Feb 08, 2015 04:59:56 PM
思路:
首先bfs求出每个空地到每个门的最短距离,注意中间不能经过任何门.好像是原题说过只要经过门就算是退出了.
随后我们二分答案,从原点到每块空地连容量为1的边,从每扇门到汇点连容量为(当前二分的答案)时间的边,对于每块空地和每扇门,若距离不超过时间,则从空地到门连一条容量为1的边.
好像唯一的trick就是从门到汇点的边?不过大家自己YY一下吧.
反正不难.
#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define N 21
#define M 21
int n,m;
char s[M];
int ty[N][M];
int d[N][M];
static const int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
struct Ins{
int x,y;
Ins(){}
Ins(int _x,int _y):x(_x),y(_y){}
};
void bfs(int x,int y){
static queue<Ins>q;
d[x][y]=0,q.push(Ins(x,y));
while(!q.empty()){
Ins tmp=q.front();q.pop();
for(int k=0;k<4;++k){
int nx=tmp.x+dx[k],ny=tmp.y+dy[k];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&ty[nx][ny]==1&&d[nx][ny]==-1)
d[nx][ny]=d[tmp.x][tmp.y]+1,q.push(Ins(nx,ny));
}
}
}
struct MaxflowSolver{
static const int V=1010,E=200010;
int head[V],next[E],end[E],flow[E],ind,d[V],inq[V];
inline void reset(){ind=0,memset(head,-1,sizeof head);}
inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
inline bool bfs(int S,int T){
static int q[V];int fr=0,ta=0;
memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
while(fr^ta){
int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
}return d[T]!=-1;
}
inline int dinic(int p,int T,int Maxflow){
if(p==T)return Maxflow;
int last=Maxflow;
for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){
int to=dinic(end[j],T,last>flow[j]?flow[j]:last);
if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;}
}d[p]=-1;return Maxflow-last;
}
inline int Maxflow(int S,int T){
int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res;
}
}Stg;
int lab[N][M];
int main(){
scanf("%d%d",&n,&m);register int i,j;
for(i=1;i<=n;++i){
scanf("%s",s+1);
for(j=1;j<=m;++j)if(s[j]=='.')ty[i][j]=1;else if(s[j]=='D')ty[i][j]=2;
}
int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j])lab[i][j]=++id;
int L=0,R=1<<30,mid;
while(L<R){
mid=(L+R)>>1;
Stg.reset();
int cnt=0;
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==1)Stg.make(0,lab[i][j],1),++cnt;
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2)Stg.make(lab[i][j],n*m+1,mid);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2){
memset(d,-1,sizeof d),bfs(i,j);
for(int p=1;p<=n;++p)for(int q=1;q<=m;++q)if(ty[p][q]==1&&d[p][q]!=-1)
if(d[p][q]<=mid)Stg.make(lab[p][q],lab[i][j],1);
}
if(Stg.Maxflow(0,n*m+1)==cnt)R=mid;else L=mid+1;
}
if(L==1<<30)puts("impossible");else printf("%d",L);
return 0;
}
BZOJ1822:[JSOI2010]Frozen Nova 冷冻波 二分+计算几何+网络流
Feb 07, 2015 09:10:58 AM
思路:
一眼网络流,套一个二分就行了.
关键是如何判断巫妖和精灵之间能否有圆阻挡.
一开始我是进行了复杂的判断:如果线段平行于x轴或者平行于y轴直接特判;
否则求出圆心到直线的距离,如果距离不超过半径,则用一个简单的公式求出圆心到直线最近点的横坐标,利用这个横坐标与线段两个端点的横坐标比较,得出结果.
可是数据跟我想的根本不是一回事啊啊啊!
根本只需要判断距离啊啊啊!!而且相切的情况不算相交啊啊啊!!
什么坑爹数据,我是领教到了.
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define N 210
#define M 210
#define P 210
struct MaxflowSolver{
static const int V=410;
static const int E=100010;
int head[V],next[E],end[E],flow[E],ind,d[V];
inline void reset(){ind=0,memset(head,-1,sizeof head);}
inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
inline bool bfs(int S,int T){
static int q[V];int fr=0,ta=0;
memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
while(fr^ta){
int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
}return d[T]!=-1;
}
inline int dinic(int p,int T,int Maxflow){
if(p==T)return Maxflow;
int last=Maxflow;
for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){
int to=dinic(end[j],T,last>flow[j]?flow[j]:last);
if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;}
}d[p]=-1;return Maxflow-last;
}
inline int Maxflow(int S,int T){
int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res;
}
}Stg;
int x1[N],y1[N],x2[M],y2[M],lim[N],cd[N],ox[P],oy[P],r[P];
int G[N][M];
inline int sqr(int x){return x*x;}
int main(){
int n,m,p;scanf("%d%d%d",&n,&m,&p);register int i,j,k;
for(i=1;i<=n;++i)scanf("%d%d%d%d",&x1[i],&y1[i],&lim[i],&cd[i]);
for(i=1;i<=m;++i)scanf("%d%d",&x2[i],&y2[i]);
for(i=1;i<=p;++i)scanf("%d%d%d",&ox[i],&oy[i],&r[i]);
int a,b,c;
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(sqr(x1[i]-x2[j])+sqr(y1[i]-y2[j])<=sqr(lim[i])){
bool ok=1;
for(k=1;k<=p&&ok;++k){
a=y1[i]-y2[j],b=x2[j]-x1[i],c=(x1[i]-x2[j])*y1[i]-(y1[i]-y2[j])*x1[i];
if((LL)(a*ox[k]+b*oy[k]+c)*(a*ox[k]+b*oy[k]+c)<(LL)r[k]*r[k]*(a*a+b*b))ok=0;
}
if(ok)G[i][j]=1;
}
int L=0,R=1<<30,mid;
while(L<R){
mid=(L+R)>>1;
Stg.reset();
for(i=1;i<=n;++i)Stg.make(0,i,mid/cd[i]+1);
for(i=1;i<=m;++i)Stg.make(n+i,n+m+1,1);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(G[i][j])Stg.make(i,n+j,1);
if(Stg.Maxflow(0,n+m+1)==m)R=mid;else L=mid+1;
}
if(L==1<<30)puts("-1");else printf("%d",L);
return 0;
}
BZOJ3774:最优选择 网络流
Feb 05, 2015 04:47:47 PM
思路:
首先由于是一个二分图,我们分为左右两部分.
...然后具体的建模自己看代码吧,真的是好神奇的思路...
我居然连这都想不出来真是混不下去了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
static const int INF=0x3f3f3f3f;
struct MaxflowSolver{
static const int V=5010;
static const int E=80010;
int head[V],next[E],end[E],flow[E],ind;
int d[V];
inline void reset(){ind=0,memset(head,-1,sizeof head);}
inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
inline bool bfs(int S,int T){
static int q[V];int fr=0,ta=0;
memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
while(fr^ta){
int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
}return d[T]!=-1;
}
inline int dinic(int p,int T,int Maxflow){
if(p==T)return Maxflow;
int last=Maxflow;
for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[p]+1==d[end[j]]){
int to=dinic(end[j],T,last>flow[j]?flow[j]:last);if(to)flow[j]-=to,flow[j^1]+=to,last-=to;
if(!last)return Maxflow;
}
d[p]=-1;return Maxflow-last;
}
inline int Maxflow(int S,int T){
int res=0;
while(bfs(S,T))res+=dinic(S,T,INF);
return res;
}
}Stg;
int lab[51][51][2],a[51][51],b[51][51];
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int main(){
int n,m;scanf("%d%d",&n,&m);register int i,j,k;int x,res=0;
int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)lab[i][j][0]=++id,lab[i][j][1]=++id;
for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&a[i][j]);
for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&b[i][j]),res+=b[i][j];
int S=0,T=id+1;
Stg.reset();
for(i=1;i<=n;++i)for(j=1;j<=m;++j){
if((i+j)&1)Stg.make(S,lab[i][j][0],a[i][j]),Stg.make(lab[i][j][0],lab[i][j][1],b[i][j]);
else Stg.make(lab[i][j][1],lab[i][j][0],b[i][j]),Stg.make(lab[i][j][0],T,a[i][j]);
for(k=0;k<4;++k){
int nowx=i+dx[k],nowy=j+dy[k];
if(nowx>=1&&nowx<=n&&nowy>=1&&nowy<=m){
if((i+j)&1)Stg.make(lab[i][j][0],lab[nowx][nowy][1],INF);
else Stg.make(lab[nowx][nowy][1],lab[i][j][0],INF);
}
}
}
printf("%d",res-Stg.Maxflow(S,T));
return 0;
}