传送门:

BZOJ

洛谷


Description

高一一班的座位表是个n \times m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。


Input

第一行两个正整数n,m。接下来是六个矩阵第一个矩阵为nm列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。第二个矩阵为第n行第m列此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择理科获得的喜悦值。第三个矩阵为n-1m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择文科获得的额外喜悦值。第四个矩阵为n-1m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择理科获得的额外喜悦值。第五个矩阵为第n行第m-1列此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择文科获得的额外喜悦值。第六个矩阵为nm-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择理科获得的额外喜悦值。

Output

输出一个整数,表示喜悦值总和的最大值


Sample Input

1 2
1 1
100 110
1
1000

Sample Output

1210

【样例说明】

两人都选理,则获得100+110+1000的喜悦值。

数据规模】

对于 100 \%以内的数据,n,m \le 100 所有喜悦值均为小于等于5000的非负整数


传送门:

网络流经典题。

我们对于点(i,j),从S(i,j)连一条容量为选择文科的喜悦值的边,从(i,j)T连一条容量为选择理科的喜悦值的边。

对于额外的奖励,假设(i,j)(i,j+1)进行组合。我们就新建一个节点,从源点向这个节点连一条容量为两者同选文科/理科的喜悦值的边,然后由这个点向(i,j)(i,j+1)分别连一条容量为INF的边。其余的组合同理。

Code:

/*Program from Luvwgyx*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1e9;
const int maxn=1e5+10;
const int maxm=5e6+10;
queue<int >q;
struct node{int to,nxt,w;}e[maxm];
int n,m,S,T,tot=1,sum,cnt,maxflow,head[maxn],d[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int get(int x,int y){return (x-1)*m+y;}
void add(int u,int v,int w){
    e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;
    e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
bool bfs(){
    memset(d,0,sizeof(d));
    while(!q.empty())q.pop();
    q.push(S);d[S]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
            if(e[i].w&&!d[v]){
                q.push(v);d[v]=d[x]+1;
                if(v==T)return 1;
            }
    }return 0;
}
int dinic(int x,int flow){
    if(x==T)return flow;
    int rest=flow,w;
    for(int i=head[x],v=e[i].to;i&&rest;i=e[i].nxt,v=e[i].to)
        if(e[i].w&&d[v]==d[x]+1){
            w=dinic(v,min(rest,e[i].w));
            if(!w)d[v]=0;
            e[i].w-=w;e[i^1].w+=w;rest-=w;
        }
    return flow-rest;
}
int main(){
    n=read();m=read();S=0;T=2*n*m+2*(n-1)*m+2*n*(m-1)+1;cnt=n*m;int x;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){x=read();sum+=x;add(S,get(i,j),x);}
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){x=read();sum+=x;add(get(i,j),T,x);}
    for(int i=1;i<n;i++) for(int j=1;j<=m;j++){x=read();sum+=x;add(S,++cnt,x);add(cnt,get(i,j),inf);add(cnt,get(i+1,j),inf);}
    for(int i=1;i<n;i++) for(int j=1;j<=m;j++){x=read();sum+=x;add(++cnt,T,x);add(get(i,j),cnt,inf);add(get(i+1,j),cnt,inf);}
    for(int i=1;i<=n;i++)for(int j=1;j<m;j++) {x=read();sum+=x;add(S,++cnt,x);add(cnt,get(i,j),inf);add(cnt,get(i,j+1),inf);}
    for(int i=1;i<=n;i++)for(int j=1;j<m;j++) {x=read();sum+=x;add(++cnt,T,x);add(get(i,j),cnt,inf);add(get(i,j+1),cnt,inf);}
    while(bfs())maxflow+=dinic(S,inf);write(sum-maxflow);
    return 0;
}