1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 30005, M = 300005, inf = 1 << 30;
int n, m, s, t, head[N], cnt = 1, dis[N], now[N], tot;
struct E {
int nxt, v, w;
} e[M];
void add(int u, int v, int w) {
e[++cnt] = {head[u], v, w}; head[u] = cnt;
e[++cnt] = {head[v], u, 0}; head[v] = cnt;
}
bool bfs() {
for (int i = 1; i <= tot; i++) dis[i] = inf;
dis[s] = 0;
now[s] = head[s];
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (dis[v] == inf && e[i].w > 0) {
dis[v] = dis[u] + 1;
now[v] = head[v];
q.push(v);
if (v == t) return 1;
}
}
}
return 0;
}
int dfs(int u, int sum) {
if (u == t) return sum;
int k, res = 0;
for (int i = now[u]; i && sum; i = e[i].nxt) {
int v = e[i].v;
now[u] = i;
if (dis[v] == dis[u] + 1 && e[i].w > 0) {
k = dfs(v, min(sum, e[i].w));
if (k == 0) dis[v] = inf;
e[i].w -= k;
e[i ^ 1].w += k;
res += k;
sum -= k;
}
}
return res;
}
ll dinic(int s, int t) {
ll res = 0;
while (bfs()) res += dfs(s, inf);
return res;
}
int pos(int i, int j) { return (i - 1) * m + j; }
int main() {
ll res = 0;
scanf("%d %d", &n, &m);
tot = n * m;
s = ++tot, t = ++tot;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int x;
scanf("%d", &x);
res += x;
add(s, pos(i, j), x);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int x;
scanf("%d", &x);
res += x;
add(pos(i, j), t, x);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int ss = ++tot, x;
scanf("%d", &x);
res += x;
add(s, ss, x);
add(ss, pos(i, j), inf);
if (i > 1) add(ss, pos(i - 1, j), inf);
if (j > 1) add(ss, pos(i, j - 1), inf);
if (i < n) add(ss, pos(i + 1, j), inf);
if (j < m) add(ss, pos(i, j + 1), inf);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int tt = ++tot, x;
scanf("%d", &x);
res += x;
add(tt, t, x);
add(pos(i, j), tt, inf);
if (i > 1) add(pos(i - 1, j), tt, inf);
if (j > 1) add(pos(i, j - 1), tt, inf);
if (i < n) add(pos(i + 1, j), tt, inf);
if (j < m) add(pos(i, j + 1), tt, inf);
}
printf("%d\n", res - dinic(s, t));
return 0;
}
|