happiness

思路：

从\(s\)向\((i,j)\)连边\(v_文(i,j),\)从\((i,j)\)向\(t\)连边\(v_理(i,j),\)从\(s\)向辅助点\(x\)连边\(v_{同文}((i,j),(i-1,j))\)，从\(x\)向\((i,j),(i-1,j)\)连边\(inf,\)同理\(,\)向四周\(、\)同文同理建立关系

证明：

先求总贡献\((\sum_{i=1}^mv_{文...})，\)减去最小的非法贡献\((\)最小割\()\)

\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
# define read read1<int>()
# define Type template<typename T>
Type inline T read1(){
    T n=0;
    char k;
    bool fl=0;
    do (k=getchar())=='-'&&(fl=1);while('9'<k||k<'0');
    while(47<k&&k<58)n=(n<<3)+(n<<1)+(k^48),k=getchar();
    return fl?-n:n;
}
class Flow{
    # define Big 74001
    # define Big2 300000
    # define Imax 2e9
    private:
        int cur[Big+1],q[Big+1],lev[Big+1];
        class Pic{
            public:
                class Edge{
                    public:
                        int u,t;
                        double v;
                }G[Big2<<1|1];
                int f[Big+1],tot;
                Pic(){for(int i=0;i<=Big;++i)f[i]=0;tot=0;}
                void add(int u,int v,double t){
                    G[++tot].u=v;
                    G[tot].t=f[u];
                    f[u]=tot;
                    G[tot].v=t;
                }
        }G;
    public:
        int S,T,n;
        void Clear(){memset(G.f,0,sizeof(G.f));G.tot=0;}
        Flow(int big,int s,int t){n=big;S=s;T=t;}
        void Into(int s,int t){S=s;T=t;}
        void add(int u,int v,double t){
            G.add(u,v,t);G.add(v,u,0);
        }
        bool bfs(){
            for(int i=0;i++^n;lev[i]=0);
            lev[S]=1;int t=0;
            q[t++]=S;
            for(int i=0;i^t;++i){
                int u=q[i];
                for(int i=G.f[u];i;i=G.G[i].t){
                    if(!lev[G.G[i].u]&&G.G[i].v>0){
                        int to=G.G[i].u;
                        lev[to]=lev[u]+1;
                        q[t++]=to;
                        if(to==T)return 1;
                    }
                }
            }
            return 0;
        }
        double dfs(int u,double f){
            if(u==T)return f;
            double tag=0,c;
            for(int &i=cur[u];i;i=G.G[i].t){
                int to=G.G[i].u;
                if(G.G[i].v>0&&lev[to]==lev[u]+1){
                    c=dfs(to,min(f-tag,G.G[i].v));
                    G.G[i].v-=c;
                    G.G[(i-1^1)+1].v+=c;
                    tag+=c;
                    if(tag==f)return tag;
                }
            }
            return tag;
        }
        double Dinic(){
            double ans=0;
            while(bfs()){
                for(int i=0;i++^n;)cur[i]=G.f[i];
                ans+=dfs(S,2e9);
            }
            return ans;
        }
    # undef Big
    # undef Big2
};
int n=read,m=read,tot,t,l;
Flow G(n*m*6+10,1,2);
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define f(i,l,r) for(int i=l;i<=r;++i)
int Hash(int x,int y){return (x-1)*m+y;}
int main(){
    //fre("..\\1");
    tot=n*m+2;
    f(i,1,n)f(j,1,m)G.add(1,Hash(i,j)+2,l=read),t+=l;
    f(i,1,n)f(j,1,m)G.add(Hash(i,j)+2,2,l=read),t+=l;
    f(i,1,n-1)f(j,1,m)G.add(1,++tot,l=read),G.add(tot,Hash(i,j)+2,Imax),G.add(tot,Hash(i+1,j)+2,Imax),t+=l;
    f(i,1,n-1)f(j,1,m)G.add(++tot,2,l=read),G.add(Hash(i,j)+2,tot,Imax),G.add(Hash(i+1,j)+2,tot,Imax),t+=l;
    f(i,1,n)f(j,1,m-1)G.add(1,++tot,l=read),G.add(tot,Hash(i,j)+2,Imax),G.add(tot,Hash(i,j+1)+2,Imax),t+=l;
    f(i,1,n)f(j,1,m-1)G.add(++tot,2,l=read),G.add(Hash(i,j)+2,tot,Imax),G.add(Hash(i,j+1)+2,tot,Imax),t+=l;
    printf("%.0f\n",t-G.Dinic());
    return 0;
}