文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠

结过）

 小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行

描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择

一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式

得到：

．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如

  果选择理科，将得到science[i][j]的满意值。

．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且

  仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开

  心，所以会增加same_art[i][j]的满意值。

．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理

  科，则增加same_science[i]j[]的满意值。

  小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请

告诉他这个最大值。

Input

第一行为两个正整数：n，m

接下来n术m个整数，表示art[i][j]；

接下来n术m个整数．表示science[i][j]；

接下来n术m个整数，表示same_art[i][j]；

Output

输出为一个整数，表示最大的满意值之和

Sample Input

Sample Output

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

const int inf=;

int N,M,S,T,ans,maxflow;

int Laxt[maxn],To[maxn],Next[maxn],cap[maxn],cnt=;

int vd[maxn],dis[maxn];

int xx[]={,,,,-};

int yy[]={,,-,,};

void add(int u,int v,int c)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

    cap[cnt]=c;

}

int id(int u,int v){

    return (u-)*M+v;

}

int sap(int u,int flow)

{

    if(flow==||u==T) return flow;

    int tmp,delta=;

    for(int i=Laxt[u];i;i=Next[i]){

        if(dis[u]==dis[To[i]]+&&cap[i]>){

           tmp=sap(To[i],min(cap[i],flow-delta));

            delta+=tmp;

           cap[i]-=tmp;

           cap[i^]+=tmp;

           if(delta==flow||dis[S]>T+) return delta;

        }

    }

    vd[dis[u]]--;

    if(vd[dis[u]]==) dis[S]=T+;

    vd[++dis[u]]++;

    return delta;

}

int main()

{

    int i,j,k,x; scanf("%d%d",&N,&M);

    S=; T=*N*M+;

    for(i=;i<=N;i++)

     for(j=;j<=M;j++){

        scanf("%d",&x); ans+=x;

        add(S,id(i,j),x); add(id(i,j),S,);

    }

    for(i=;i<=N;i++)

     for(j=;j<=M;j++){

         scanf("%d",&x); ans+=x;

         add(id(i,j),T,x); add(T,id(i,j),);

     }

    for(i=;i<=N;i++)

     for(j=;j<=M;j++){

         scanf("%d",&x); ans+=x;

         add(S,N*M+id(i,j),x); add(N*M+id(i,j),S,);

         for(k=;k<=;k++){

             int x=i+xx[k],y=j+yy[k];

             if(x>=&&x<=N&&y>=&&y<=M){

                 add(N*M+id(i,j),id(x,y),inf); add(id(x,y),N*M+id(i,j),);

             }

         }

     }

    for(i=;i<=N;i++)

     for(j=;j<=M;j++){

         scanf("%d",&x); ans+=x;

         add(*N*M+id(i,j),T,x); add(T,*N*M+id(i,j),);

         for(k=;k<=;k++){

             int x=i+xx[k],y=j+yy[k];

             if(x>=&&x<=N&&y>=&&y<=M){

                 add(id(x,y),*N*M+id(i,j),inf); add(*N*M+id(i,j),id(x,y),);

             }

         }

     }

     while(dis[S]<=T) maxflow+=sap(S,inf);

     printf("%d\n",ans-maxflow);

     return ;

}