「BJOI 2006」狼抓兔子【最小割】

Time Limit: 15 Sec Memory Limit: 192 MB

Description

左上角点为 (1,1)(1, 1),右下角点为 (N,M)(N, M)。有以下三种类型的道路:

  1. (x,y)(x+1,y)(x, y) \longleftrightarrow (x+1, y)
  2. (x,y)(x,y+1)(x, y) \longleftrightarrow (x, y+1)
  3. (x,y)(x+1,y+1)(x, y) \longleftrightarrow (x+1, y+1)

道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的。左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角 (1,1)(1, 1) 的窝里,现在它们要跑到右下角 (N,M)(N, M) 的窝中去,狼王开始伏击这些兔子。当然为了保险起见,如果一条道路上最多通过的兔子数为 KK,狼王需要安排同样数量的 KK 只狼,才能完全封锁这条道路。你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。

网格图示

Input

第一行为 N,MN, M,表示网格的大小,其中 N,MN, M 均小于等于 10001000

接下来分三部分:

  • 第一部分共 NN 行,每行 M1M - 1 个数,表示横向道路的权值。
  • 第二部分共 N1N - 1 行,每行 MM 个数,表示纵向道路的权值。
  • 第三部分共 N1N - 1 行,每行 M1M - 1 个数,表示斜向道路的权值。

Output

输出一个整数,表示参与伏击的狼的最小数量。

Sample Input

1
2
3
4
5
6
7
8
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

Sample Output

1
14

Solution

最小割:给定一个网络 G=(V,E)G = (V, E),源点为 SS,汇点为 TT。若一个边集 EEE' \subseteq E 被删去之后,源点 SS 和汇点 TT 不再连通,则称该边集为网络的。边的容量之和最小的割称为网络的最小割

最大流最小割定理:任何一个网络的最大流量等于最小割中边的容量之和,简记为:最大流 == 最小割。(证明略)

题意是求一个无向图的最小割,用 Dinic\text {Dinic} 算法求出最大流即为答案。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000010;
struct edge {
int to, cap, nxt;
} e[maxn * 6];
int n, m, x, cnt, head[maxn], level[maxn];

int id(int x, int y) {
return (x - 1) * m + y;
}

void add_edge(int from, int to, int cap) {
e[cnt] = (edge){to, cap, head[from]}, head[from] = cnt++;
e[cnt] = (edge){from, cap, head[to]}, head[to] = cnt++;
}

int bfs(int s, int t) {
fill(level + 1, level + n * m + 1, 0);
queue<int> q;
level[s] = 1;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = head[v]; i != -1; i = e[i].nxt) {
if (e[i].cap > 0 && !level[e[i].to]) {
level[e[i].to] = level[v] + 1;
q.push(e[i].to);
}
}
}
return level[t];
}

int dfs(int v, int t, int f) {
if (v == t) {
return f;
}
int add = 0;
for (int i = head[v]; i != -1 && add < f; i = e[i].nxt) {
if (e[i].cap > 0 && level[v] + 1 == level[e[i].to]) {
int d = dfs(e[i].to, t, min(e[i].cap, f - add));
if (d > 0) {
e[i].cap -= d;
e[i ^ 1].cap += d;
add += d;
} else {
level[e[i].to] = -1;
}
}
}
return add;
}

int dinic(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
flow += dfs(s, t, 0x3f3f3f3f);
}
return flow;
}

int main() {
scanf("%d %d", &n, &m);
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; i++) {
for (int j = 1; j < m; j++) {
scanf("%d", &x);
add_edge(id(i, j), id(i, j + 1), x);
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &x);
add_edge(id(i, j), id(i + 1, j), x);
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
scanf("%d", &x);
add_edge(id(i, j), id(i + 1, j + 1), x);
}
}
printf("%d\n", dinic(id(1, 1), id(n, m)));
return 0;
}