「BZOJ2127」happiness

Description

高一一班的座位表是个n×mn\times m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。

作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。

Input

第一行两个正整数nnmm

接下来是六个矩阵

第一个矩阵为nnmm
此矩阵的第ii行第jj列的数字表示座位在第ii行第jj列的同学选择文科获得的喜悦值。

第二个矩阵为nnmm
此矩阵的第ii行第jj列的数字表示座位在第ii行第jj列的同学选择理科获得的喜悦值。

第三个矩阵为n-1行mm
此矩阵的第ii行第jj列的数字表示座位在第ii行第jj列的同学与第i+1i+1行第jj列的同学同时选择文科获得的额外喜悦值。

第四个矩阵为n-1行mm
此矩阵的第ii行第jj列的数字表示座位在第ii行第jj列的同学与第i+1i+1行第jj列的同学同时选择理科获得的额外喜悦值。

第五个矩阵为nnm1m-1
此矩阵的第ii行第jj列的数字表示座位在第ii行第jj列的同学与第ii行第j+1j+1列的同学同时选择文科获得的额外喜悦值。

第六个矩阵为nnm1m-1
此矩阵的第ii行第jj列的数字表示座位在第ii行第jj列的同学与第ii行第j+1j+1列的同学同时选择理科获得的额外喜悦值。

Output

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

Sample Input

1
2
3
4
5
1 2
1 1
100 110
1
1000

Sample Output

1
1210

HINT

两人都选理,则获得100+110+1000100+110+1000的喜悦值。
对于100%100\%以内的数据,n,m100n,m\leq 100 所有喜悦值均为小于等于50005000的非负整数

Solution


盗来一张图,建立新点,如果artart有任意一个被割掉,那么被割的那个点对应的scisci必定没被割掉,如果想要让artart割掉有效果,那么artsameart_same也要相同。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 120, M = N * N * 2;
struct Edge {
int u, v, nxt, f;
}e[M * 6 * 3];
int head[N * N*5], en = 1;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
int s, t, tot;
int d[N * N*5];
bool bfs() {
queue<int>q;
for(int i = 1; i <= tot; ++i) d[i] = 0;
d[s] = 1;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f && !d[e[i].v]) {
d[e[i].v] = d[x] + 1;
if(e[i].v == t) return 1;
q.push(e[i].v);
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; i && rest; i = e[i].nxt) if(e[i].f && d[e[i].v] == d[x] + 1) {
int y = e[i].v;
k = dinic(y, min(rest, e[i].f));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
if(rest == flow) d[x] = 0;
return flow - rest;
}
const int inf = 1e9;
int n, m;
int id(int x, int y) {
return (x - 1) * m + y;
}
int solve() {
int res = 0, y;
while(bfs()) while(y = dinic(s, inf)) res += y;
return res;
}
int main() {
n = read(), m = read();
s = n * m + 1;
t = n * m + 2;
tot = t;
int sum = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
int x = read();
addedge(s, id(i, j), x);
sum += x;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
int x = read();
addedge(id(i, j), t, x);
sum += x;
}
for(int i = 1; i < n; ++i)
for(int j = 1; j <= m; ++j) {
int x = read();
addedge(s, ++tot, x);
addedge(tot, id(i, j), inf);
addedge(tot, id(i + 1, j), inf);
sum += x;
}
for(int i = 1; i < n; ++i)
for(int j = 1; j <= m; ++j) {
int x = read();
addedge(++tot, t, x);
addedge(id(i, j), tot, inf);
addedge(id(i + 1, j), tot, inf);
sum += x;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j < m; ++j) {
int x = read();
addedge(s, ++tot, x);
addedge(tot, id(i, j), inf);
addedge(tot, id(i, j + 1), inf);
sum += x;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j < m; ++j) {
int x = read();
addedge(++tot, t, x);
addedge(id(i, j), tot, inf);
addedge(id(i, j + 1), tot, inf);
sum += x;
}
writeln(sum - solve());
return 0;
}