数据范围一眼网络流。
考虑每个人文理只能选一个，考虑最小割。
考虑源点\(S\)向\((i,j)\)连一条费用为\(art_{i,j}\)的边，\((i,j)\)向汇点\(T\)连一条费用为\(science_{i,j}\)的边。若割\(S\)与\((i,j)\)的边，则表示\((i,j)\)不选文，若割\((i,j_\)与\(T\)的边，则表示\((i,j)\)不选理。
然后考虑相邻的人都选文的情况，新建一个点\(cnt\)，不妨设这个\(cnt\)表示\((i,j)\)及\((i,j)\)相邻的人都选了文的情况，则源点\(S\)向\(cnt\)连一条\(same_art_{i,j}\)的边，\(cnt\)分别向向\((i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)\)连一条费用为\(inf\)的边，若割掉源点\(S\)与\(cnt\)的边，表示这五个不全选文
相邻的人选理的情况同理，只不过是向汇点连罢了。
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=3e5+50,hd=1e9,INF=1e15;
ll n,m,zh,s,t,sr,cnt,ans;
ll h[N],e[N],ne[N],w[N],idx=1;
void add(ll a,ll b,ll c)
{
e[++idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
e[++idx]=a;
w[idx]=0;
ne[idx]=h[b];
h[b]=idx;
}
ll dep[N],now[N];
bool bfs()
{
for(ll i=0;i<=cnt;i++) dep[i]=INF;
dep[s]=1;
queue<ll> q;
q.push(s);
now[s]=h[s];
while(!q.empty())
{
ll wz=q.front();
q.pop();
for(ll i=h[wz];i;i=ne[i])
{
ll j=e[i];
if(w[i]==0) continue;
if(dep[j]==INF)
{
now[j]=h[j];
dep[j]=dep[wz]+1;
q.push(j);
if(j==t) return true;
}
}
}
return false;
}
ll dfs(ll wz,ll k)
{
if(wz==t) return k;
ll sum,res=0;
for(ll i=now[wz];i&&k;i=ne[i])
{
now[wz]=i;
ll j=e[i];
if(w[i]==0||dep[j]!=dep[wz]+1) continue;
sum=dfs(j,min(k,w[i]));
if(sum==0) dep[j]=INF;
res+=sum;
k-=sum;
w[i]-=sum;
w[i^1]+=sum;
}
return res;
}
int main()
{
scanf("%lld %lld",&n,&m);
s=0,t=1,cnt=n*m+1;
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
scanf("%lld",&sr);
zh+=sr;
add(s,(i-1)*m+j+1,sr);
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
scanf("%lld",&sr);
zh+=sr;
add((i-1)*m+j+1,t,sr);
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
scanf("%lld",&sr);
zh+=sr;
cnt++;
add(s,cnt,sr);
add(cnt,(i-1)*m+j+1,sr);
if(i!=1) add(cnt,(i-2)*m+j+1,hd);
if(i!=n) add(cnt,i*m+j+1,hd);
if(j!=1) add(cnt,(i-1)*m+j,hd);
if(j!=m) add(cnt,(i-1)*m+j+2,hd);
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
scanf("%lld",&sr);
zh+=sr;
cnt++;
add(cnt,t,sr);
add((i-1)*m+j+1,cnt,sr);
if(i!=1) add((i-2)*m+j+1,cnt,hd);
if(i!=n) add(i*m+j+1,cnt,hd);
if(j!=1) add((i-1)*m+j,cnt,hd);
if(j!=m) add((i-1)*m+j+2,cnt,hd);
}
}
while(bfs()) ans+=dfs(s,INF);
printf("%lld\n",zh-ans);
return 0;
}