学步园

#include<iostream>
#include<cstring>
#include<cstdio>
#define INF 0x7fffffff
using namespace std;
struct data{
    int to,next,v;
}e[6000001];
int n,m,ne=1,ans,head[1000001],h[1000001],q[1000001];
void insert(int u,int v,int w){
    e[++ne].to=v;
    e[ne].next=head[u];
    e[ne].v=w;
    head[u]=ne;
}
bool bfs(){
    memset(h,-1,sizeof(h));
    h[1]=0;q[0]=1;
    int i,now,t=0,w=1;
    while(t<w){
        now=q[t++];
        i=head[now];
        while(i){
            if(e[i].v&&h[e[i].to]==-1){
                q[w++]=e[i].to;
                h[e[i].to]=h[now]+1;
            }
            i=e[i].next;
        }
    }
    if(h[n*m]==-1)return false;
    else return true;
}
int dfs(int x,int f){
    if(x==n*m)return f;
    int w,i=head[x],used=0;
    while(i){
        if(e[i].v&&h[e[i].to]==h[x]+1){
            w=f-used;
            w=dfs(e[i].to,min(e[i].v,w));
            e[i].v-=w;
            e[i+1].v+=w;
            used+=w;
            if(used==f)return f;
        }
        i=e[i].next;
    }
    if(!used)h[x]=-1;
    return used;
}
void dinic(){
    while(bfs())ans+=dfs(1,INF);
}
int main(){
    scanf("%d %d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++){
            scanf("%d",&x);
            insert(m*(i-1)+j,m*(i-1)+j+1,x);
            insert(m*(i-1)+j+1,m*(i-1)+j,x);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&x);
            insert(m*(i-1)+j,m*(i)+j,x);
            insert(m*(i)+j,m*(i-1)+j,x);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++){
            scanf("%d",&x);
            insert(m*(i-1)+j,m*(i)+j+1,x);
            insert(m*(i)+j+1,m*(i-1)+j,x);
        }
    dinic();
    printf("%d",ans);
    return 0;
}