题目链接：传送门

Description

左上角点为 (1,1)(1,1)，右下角点为 (n,m)(n,m)，有以下三种类型的道路：

  1. (x,y)⇔(x+1,y)(x, y) \Leftrightarrow (x + 1, y)
  2. (x,y)⇔(x,y+1)(x, y) \Leftrightarrow (x, y + 1)
  3. (x,y)⇔(x+1,y+1)(x, y) \Leftrightarrow (x + 1, y + 1)

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

Constraints

n,m≤1000n,m \leq 1000

Solution

题意就是求最小割

正解是平面图转对偶图，实际上直接暴力上Dinic在加上一点玄学(优化)居然也能过

相当于是复习一下Dinic板子吧

Code

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

const int Maxn = 1e6 + 100, Maxm = 6e6 + 100, inf = 0x3f3f3f3f;

int N, M;

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

namespace Dinic
{
	int e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm];
	int level[Maxn], Cur[Maxn];

	inline void init ()
	{
		memset(Begin, 0, sizeof Begin);
		e = 1;
	}

	inline void add_edge (int x, int y, int z)
	{
//		if (z) cout<<x<<" "<<y<<" "<<z<<endl;
		To[++e] = y;
		Next[e] = Begin[x];
		Begin[x] = e;
		W[e] = z;
	}

	inline int bfs ()
	{
		memset(level, -1, sizeof level);
		static queue <int> Q;
		Q.push(1);
		level[1] = 0;
		while (!Q.empty())
		{
			int x = Q.front(); Q.pop();
			for (int i = Begin[x]; i; i = Next[i])
			{
				int y = To[i];
				if (W[i] > 0 && level[y] < 0)
				{
					level[y] = level[x] + 1;
					Q.push(y);
				}
			}
		}
		if (level[id(N, M)] < 0) return 0;
		return 1;
	}

	inline int find (int x, int now)
	{
		if (x == id(N, M) || !now) return now;
		int sum = 0;
		for (int &i = Cur[x]; i; i = Next[i])
		{
			int y = To[i];
			if (W[i] > 0 && level[y] == level[x] + 1)
			{
				int tmp = find(y, min(now, W[i]));
				W[i] -= tmp;
				W[i ^ 1] += tmp;
				now -= tmp, sum += tmp;
				if (!now) break;
			}
		}
		if (!sum) level[x] = -1;
		return sum;
	}

	int main()
	{
		int ans = 0, sum;
		while (bfs())
		{
			for (int i = 1; i <= id(N, M); ++i) Cur[i] = Begin[i];
			while (sum = find(1, inf)) ans += sum;
		}
		return ans;
	}
}

int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	N = read(), M = read();
	Dinic :: init();
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j < M; ++j)
		{
			int x = read();
			Dinic :: add_edge (id(i, j), id(i, j + 1), x);
			Dinic :: add_edge (id(i, j + 1), id(i, j), x);
		}
	for (int i = 1; i < N; ++i)
		for (int j = 1; j <= M; ++j)
		{
			int x = read();
			Dinic :: add_edge (id(i, j), id(i + 1, j), x);
			Dinic :: add_edge (id(i + 1, j), id(i, j), x);
		}
	for (int i = 1; i < N; ++i)
		for (int j = 1; j < M; ++j)
		{
			int x = read();
			Dinic :: add_edge (id(i, j), id(i + 1, j + 1), x);
			Dinic :: add_edge (id(i + 1, j + 1), id(i, j), x);
		}
	printf("%d\n", Dinic :: main());
	return 0;
}