具体做法:
拆点,简称理科文科。
然后是 same 带来收益的点,简称同理同文。
连原图边,染色跑出来发现理科和同理总是一个颜色,文科同文总是一个颜色。
所以将理科/同理当作二分图左部,文科/同文当作二分图右部,套最大点权独立集模板。
但是挂了。
#include<bits/stdc++.h>
#define sd std::
//#define int long long
#define inf 1e9+1e5
#define linf 1e18
#define il inline
#define db double
#define ldb long double
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define f(i,a,b) for(int i=(a);i>=(b);i--)
#define MIN(x,y) (x<y?x:y)
#define MAX(x,y) (x>y?x:y)
#define me(x,y) memset(x,y,sizeof x)
#define pii sd pair<int,int>
#define umap(x,y) sd unordered_map<x,y>
#define pque(x) sd priority_queue<x>
#define X first
#define Y second
#define kg putchar(' ')
#define Fr(a) for(auto it:a)
#define dbg(x) sd cout<<#x<<": "<<x<<sd endl
il int read(){int w=1,c=0;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) c=(c<<3)+(c<<1)+ch-48;return w*c;}
void printt(int x){if(x>9) printt(x/10);putchar(x%10+48);}
il void print(int x){if(x<0) putchar('-'),printt(-x);else printt(x);}
il void put(int x){print(x);putchar('\n');}
il void printk(int x){print(x);kg;}
const int N=3e6+10,M=310;
struct node
{
int nex;
int to;
int w;
}a[N],e[N];
int tot=1,head[N],now[N];
void ad(int u,int v,int w)
{
a[++tot].nex=head[u];
head[u]=tot;
a[tot].to=v;
a[tot].w=w;
}
void add(int u,int v,int w)
{
ad(u,v,w);
ad(v,u,0);
}
int d[N],n,m,s,t;
int bfs()
{
me(d,0);
d[s]=1;
sd queue<int> q;
q.push(s);
now[s]=head[s];
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=a[i].nex)
{
int v=a[i].to,w=a[i].w;
if(w&&!d[v])
{
d[v]=d[u]+1;
now[v]=head[v];
q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
int dfs(int u,int flow)
{
if(u==t||!flow) return flow;
int tmp=flow;
for(int i=now[u];i&&tmp;i=a[i].nex)
{
now[u]=i;
int v=a[i].to,w=a[i].w;
if(w&&d[v]==d[u]+1)
{
int k=dfs(v,MIN(tmp,w));
if(!k) d[v]=0;
a[i].w-=k;
a[i^1].w+=k;
tmp-=k;
}
}
return flow-tmp;
}
int dinic()
{
int ans=0;
while(bfs()) ans+=dfs(s,INT_MAX);
return ans;
}
//编号:1~r*c 理科,r*c+1~r*c+r*c 文科,r*c*2+1~r*c*3 同理,r*c*3+1~r*c*4 同文
int r,c;
int sin(int i,int j){return (i-1)*c+j;}//理科编号
int art(int i,int j){return r*c+(i-1)*c+j;}//文科编号
int sasin(int i,int j){return r*c*2+(i-1)*c+j;}//同理编号
int saart(int i,int j){return r*c*3+(i-1)*c+j;}//同文编号
int dx[5]={-1,1,0,0};
int dy[5]={0,0,-1,1};
//源点连颜色为1的,汇点连颜色为0的
il void solve()
{
r=read(),c=read();
s=0,t=r*c*4+1;
F(i,1,r) F(j,1,c)
{
add(art(i,j),sin(i,j),inf);//理科文科只能选一个
add(saart(i,j),sin(i,j),inf);//同文收益和理科只能选一个
add(art(i,j),sasin(i,j),inf);//同理收益和文科只能选一个
F(k,0,3)
{
int xx=i+dx[k];
int yy=j+dy[k];
if(xx<1||xx>r||yy<1||yy>c) continue;
add(saart(i,j),sin(xx,yy),inf);//相邻的人理科和此人同文收益只能选一个
add(art(xx,yy),sasin(i,j),inf);//相邻的人文科和此人同理收益只能选一个
}
}
int sum=0;
F(i,1,r) F(j,1,c)
{
int x=read();sum+=x;
add(s,art(i,j),x);
}
F(i,1,r) F(j,1,c)
{
int x=read();sum+=x;
add(sin(i,j),t,x);
}
F(i,1,r) F(j,1,c)
{
int x=read();sum+=x;
add(s,saart(i,j),x);
}
F(i,1,r) F(j,1,c)
{
int x=read();sum+=x;
add(sasin(i,j),t,x);
}
put(sum-dinic());
}
int main()
{
int T=1;
// T=read();
while(T--) solve();
return 0;
}
/*
1 3
4 3 1
1 5 4
3 9 2
6 9 2
*/