一眼最小割，转化成最大流来做。
然后发现点数达到10^6级别，妥妥TLE，于是需要进一步思考。
由网上大量题解可知，一个图的最大流等于它的对偶图的最短路，于是只要Dijkstra就可以了。
建图有点恶心。。。查了好长时间。。。
1 /************************************************************** 2 Problem: 1001 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:520 ms 7 Memory:94588 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 #include <queue> 14 15 using namespace std; 16 17 struct edges{ 18 int next, to, v; 19 } e[6000005]; 20 21 struct heap_node{ 22 int v, to; 23 }; 24 inline bool operator < (const heap_node &a, const heap_node &b){ 25 return a.v > b.v; 26 } 27 28 priority_queue <heap_node> h; 29 heap_node NODE; 30 int tot, S, T, n, m; 31 int d[3000005], first[3000005]; 32 char ch; 33 34 inline int read(){ 35 int x = 0, sgn = 1; 36 ch = getchar(); 37 while (ch < '0' || ch > '9'){ 38 if (ch == '-') sgn = -1; 39 ch = getchar(); 40 } 41 while (ch >= '0' && ch <= '9'){ 42 x = x * 10 + ch - '0'; 43 ch = getchar(); 44 } 45 return sgn * x; 46 } 47 48 inline void add_edge(int x, int y, int v){ 49 e[++tot].next = first[x], first[x] = tot; 50 e[tot].to = y, e[tot].v = v; 51 } 52 53 void add_Edges(const int x, const int y, const int v){ 54 add_edge(x, y, v); 55 add_edge(y, x, v); 56 } 57 58 inline void add_to_heap(const int p){ 59 for (int x = first[p]; x; x = e[x].next) 60 if (d[e[x].to] == -1){ 61 NODE.v = e[x].v + d[p], NODE.to = e[x].to; 62 h.push(NODE); 63 } 64 } 65 66 int Dijkstra(int S, int T){ 67 memset(d, -1, sizeof(d)); 68 while (!h.empty()) h.pop(); 69 d[S] = 0, add_to_heap(S); 70 int p; 71 while (d[T] == -1){ 72 while (d[h.top().to] != -1) h.pop(); 73 p = h.top().to; 74 d[p] = h.top().v; 75 h.pop(); 76 add_to_heap(p); 77 } 78 return d[T]; 79 } 80 81 void build_graph(){ 82 int Cost, x, y; 83 for (int i = 1; i <= n; ++i) 84 for (int j = 1; j < m; ++j){ 85 Cost = read(); 86 x = i == 1 ? S : (2 * i - 3) * (m - 1) + j; 87 y = i == n ? T : (2 * i - 2) * (m - 1) + j; 88 add_Edges(x, y, Cost); 89 } 90 for (int i = 1; i < n; ++i) 91 for (int j = 1; j <= m; ++j){ 92 Cost = read(); 93 x = j == 1 ? T : 2 * (i - 1) * (m - 1) + j - 1; 94 y = j == m ? S : 2 * (i - 1) * (m - 1) + j - 1 + m; 95 add_Edges(x, y, Cost); 96 } 97 for (int i = 1; i < n; ++i) 98 for (int j = 1; j < m; ++j){ 99 Cost = read(); 100 x = (2 * i - 2) * (m - 1) + j; 101 y = (2 * i - 1) * (m - 1) + j; 102 add_Edges(x, y, Cost); 103 } 104 } 105 106 int main(){ 107 n = read(), m = read(); 108 if (n == 1 && m == 1){ 109 printf("%d ", 0); 110 return 0; 111 } 112 113 S = 0, T = 2 * (m - 1) * (n - 1) + 1; 114 build_graph(); 115 printf("%d ", Dijkstra(S, T)); 116 return 0; 117 }