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
| #include <cstdio>
#include <queue>
#include <cstring>
const int INF = 1e9;
const int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, -1, 1, 1, -1, -1, 1};
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
int to, nxt, cap, cost;
} e[20005];
int head[2005], cur[2005], dis[2005], tot = 1, s, t, sum2;
bool vis[2005], mark[2005];
std::queue<int> Q;
inline void AddEdge(int u, int v, int cap, int cost) {
e[++ tot].to = v, e[tot].cap = cap, e[tot].cost = cost;
e[tot].nxt = head[u], head[u] = tot;
e[++ tot].to = u, e[tot].cap = 0, e[tot].cost = -cost;
e[tot].nxt = head[v], head[v] = tot;
}
bool SPFA() {
memcpy(cur, head, sizeof cur);
memset(vis, 0, sizeof vis);
memset(mark, 0, sizeof mark);
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
Q.push(s);
while (Q.size()) {
int u = Q.front();
Q.pop();
mark[u] = false;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (e[i].cap && dis[u] + e[i].cost < dis[v]) {
dis[v] = dis[u] + e[i].cost;
if (!mark[v]) mark[v] = true, Q.push(v);
}
}
}
return dis[t] <= INF;
}
int dfs(int u, int flow) {
if (u == t) return flow;
vis[u] = true;
int used = 0, tmp = 0;
for (int &i = cur[u]; i; i = e[i].nxt)
if (e[i].cap && !vis[e[i].to] && dis[u] + e[i].cost == dis[e[i].to]) {
tmp = dfs(e[i].to, min(e[i].cap, flow - used));
e[i].cap -= tmp, e[i ^ 1].cap += tmp, used += tmp;
if (used == flow) return used;
}
return used;
}
int Dinic() {
int Maxflow = 0, Mincost = 0, flow = 0;
while (SPFA()) Maxflow += (flow = dfs(s, INF)), Mincost += flow * dis[t];
return Maxflow == sum2 ? Mincost : -1;
}
char str[25];
int a[25][25], b[25][25], lim[25][25];
int main() {
int n, m, sum = 0;
scanf("%d%d", &n, &m);
s = 0, t = n * m * 3 + 1;
for (int i = 1; i <= n; ++ i) {
scanf("%s", str + 1);
for (int j = 1; j <= m; ++ j) sum += (a[i][j] = str[j] - '0'), sum2 += a[i][j];
}
for (int i = 1; i <= n; ++ i) {
scanf("%s", str + 1);
for (int j = 1; j <= m; ++ j) sum -= (b[i][j] = str[j] - '0');
}
for (int i = 1; i <= n; ++ i) {
scanf("%s", str + 1);
for (int j = 1; j <= m; ++ j) lim[i][j] = str[j] - '0';
}
if (sum) return puts("-1"), 0;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j) {
int p = (i - 1) * m + j;
if (a[i][j] == 1 && b[i][j] == 1) a[i][j] = b[i][j] = 0, -- sum2;
if (a[i][j]) AddEdge(s, p + n * m, 1, 0);
if (b[i][j]) AddEdge(p + n * m, t, 1, 0);
AddEdge(p, p + n * m, lim[i][j] + b[i][j] >> 1, 1);
AddEdge(p + n * m, p + 2 * n * m, lim[i][j] + a[i][j] >> 1, 1);
for (int k = 0; k <= 7; ++ k) {
int x = i + dx[k], y = j + dy[k];
if (x < 1 || y < 1 || n < x || m < y) continue;
AddEdge(p + 2 * n * m, (x - 1) * m + y, INF, 0);
}
}
int ans = Dinic();
printf("%d", ans == -1 ? -1 : ans / 2);
return 0;
}
|