要分成两坨对吧。。 所以显然最小割
但是不兹辞啊。。
最小割是最小的啊 求最大费用怎么玩啊
那咱们就把所有费用都加起来，减掉一个最小的呗
但是两个属于不同集合的点贡献的价值是负的啊
网络流怎么跑负的啊
那咱就交换一下呗
原图是二分图啊，把另一部分与S和T连边的流量换一下就好啦。
注意哦 n和m可能为1 所以累加C的时候写成ans += C[i][j] * (4 - (i == 1 || i == n) - (j == 1 || j == m));就错啦。
要么在加边的时候累加，要么写成ans += C[i][j] * ((i != 1) + (i != n) + (j != 1) + (j != m));
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#define rep(i, a, b) for(int i = (a), _end = (b); i <= _end; ++i) using namespace std; void setIO(const string& s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<typename Q> Q read(Q& x) {
static char c, f;
for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;
for(x = ; isdigit(c); c = getchar()) x = x * + c - '';
if(f) x = -x;
return x;
}
template<typename Q> Q read() {
static Q x; read(x); return x;
} // ISAP
const int N = * + , M = * * + , INF = ~0u >> ; struct Edge {
int to, adv;
Edge *next;
Edge(int to = , int adv = , Edge *next = ) : to(to), adv(adv), next(next) {}
}pool[M * ], *pis = pool, *fir[N], *pre[N]; void AddEdge(int u, int v, int w, int b = ) {
fir[u] = new(pis++) Edge(v, w, fir[u]);
fir[v] = new(pis++) Edge(u, w * b, fir[v]);
} Edge *inv(Edge *p) {
return pool + ((p - pool) ^ );
} int d[N], q[N], ql, qr; namespace ISAP {
int n, s, t;
int num[N];
Edge *cur[N]; void insert(int u, int dis) {
if(d[u] == n) {
d[u] = dis;
q[qr++] = u;
}
} void BFS() {
for(int u = ; u <= n; u++) {
d[u] = n;
}
ql = qr = ;
insert(t, );
while(ql ^ qr) {
int u = q[ql++];
for(Edge *p = fir[u]; p; p = p->next) if(inv(p)->adv){
insert(p->to, d[u] + );
}
}
} int Augment() {
int a = INF;
for(int u = t; u != s; u = inv(pre[u])->to) {
a = min(a, pre[u]->adv);
}
for(int u = t; u != s; u = inv(pre[u])->to) {
pre[u]->adv -= a;
inv(pre[u])->adv += a;
}
return a;
} int Maxflow() {
memset(num, , sizeof num);
BFS();
for(int u = ; u <= n; u++) {
cur[u] = fir[u];
num[d[u]]++;
}
for(int i = ; i < d[s]; i++) {
if(!num[i]) return ;
}
int flow = ;
for(int u = s; d[s] < n; ) {
if(u == t) {
flow += Augment();
u = s;
}
int ok = ;
for(Edge *&p = cur[u]; p; p = p->next) if(p->adv) {
int v = p->to;
if(d[v] + == d[u]) {
pre[u = v] = p;
ok = ;
break;
}
}
if(!ok) {
int &dis = d[u];
if(!--num[dis]) break;
dis = n;
for(Edge *p = (cur[u] = fir[u]); p; p = p->next) if(p->adv) {
dis = min(dis, d[p->to] + );
}
num[dis]++;
if(u != s) u = inv(pre[u])->to;
}
}
return flow;
} int main(int _n, int _s, int _t) {
n = _n, s = _s, t = _t;
return Maxflow();
}
} int n, m; int encode(int x, int y) {
return (x - ) * m + y;
} const int maxn = + ; int A[maxn][maxn], B[maxn][maxn], C[maxn][maxn]; int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif read(n), read(m);
int ans = ;
rep(i, , n) rep(j, , m) ans += read(A[i][j]);
rep(i, , n) rep(j, , m) ans += read(B[i][j]);
rep(i, , n) rep(j, , m) read(C[i][j]);
int s = n * m + , t = s + ;
rep(i, , n) rep(j, , m) {
int u = encode(i, j);
if((i ^ j) & ) swap(A[i][j], B[i][j]);
AddEdge(s, u, A[i][j]);
AddEdge(u, t, B[i][j]);
if(i < n) AddEdge(u, encode(i + , j), C[i][j] + C[i+][j], ), ans += C[i][j] + C[i+][j];
if(j < m) AddEdge(u, encode(i, j + ), C[i][j] + C[i][j+], ), ans += C[i][j] + C[i][j+];
} printf("%d\n", ans - ISAP::main(t, s, t)); return ;
}