如果只会用最小割做这道题那就太菜辣
引入 【对偶图与平面图|平面图转对偶图(Bzoj1001（狼抓兔子)）】来自某学长
平面图：在平面上边不相交的图（边可以绕着画）
那么平面图的边与边就围成了许多个区域（这与你画图的方式有关）
定义对偶图：把相邻的两个区域连上边，形成的图
两个可能正确的东西：
- 对偶图 ∈∈ 平面图
- 平面图的对偶图的对偶图是它自己
Sol 题目给了一个确定的平面图
考虑在起点处和终点处以它为起点画一条斜射线，把平面分成左下和右上两个部分，分别定义为 SS 和 TT
然后建立对偶图边权就是跨过的平面图的边权（ SS 和 TT 不直接相连），求一遍 SS 到 TT 的最短路即可
理解：一条 SS 到 TT 的路径把这个平面图的起点和终点隔开，那么最短路就是最小割
建图比较恶心
# include
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(6e6 + 5);
IL ll Input(){
RG ll x = 0, z = 1;
RG char c = getchar();
for(;
c < '0' || c > '9';
c = getchar()) z = c == '-' ? -1 : 1;
for(;
c >= '0' && c <= '9';
c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}int n, m, fst[_], nxt[_], w[_], to[_], cnt, dis[_], S, T, vis[_], id[1005][1005], num;
queue Q;
IL void Add(RG int u, RG int v, RG int ww){
nxt[cnt] = fst[u];
to[cnt] = v;
w[cnt] = ww;
fst[u] = cnt++;
}IL int SPFA(){
Fill(dis, 127);
dis[S] = 0;
vis[S] = 1;
Q.push(S);
while(!Q.empty()){
RG int u = Q.front();
Q.pop();
for(RG int e = fst[u];
e != -1;
e = nxt[e])
if(dis[u] + w[e] < dis[to[e]]){
dis[to[e]] = dis[u] + w[e];
if(!vis[to[e]]) vis[to[e]] = 1, Q.push(to[e]);
}
vis[u] = 0;
}
return dis[T];
}int main(RG int argc, RG char* argv[]){
Fill(fst, -1);
n = Input();
m = Input();
for(RG int i = 1, r = (n - 1) * 2;
i <= r;
++i)
for(RG int j = 1;
j < m;
++j)
id[i][j] = ++num;
T = num + 1;
for(RG int i = 1, I = 1;
i <= n;
++i, I += 2)
for(RG int j = 1;
j < m;
++j){
RG int v = Input(), id1 = S, id2 = T;
if(i != 1) id2 = id[I - 1][j];
if(i != n) id1 = id[I][j];
Add(id1, id2, v);
Add(id2, id1, v);
}
for(RG int i = 1, I = 1;
i < n;
++i, I += 2)
for(RG int j = 1;
j <= m;
++j){
RG int v = Input(), id1 = S, id2 = T;
if(j != 1) id1 = id[I][j - 1];
if(j != m) id2 = id[I + 1][j];
Add(id1, id2, v);
Add(id2, id1, v);
}for(RG int i = 1, I = 1;
i < n;
++i, I += 2)
for(RG int j = 1;
j < m;
++j){
RG int v = Input(), id1 = id[I][j], id2 = id[I + 1][j];
Add(id1, id2, v);
Add(id2, id1, v);
}
printf("%d\n", SPFA());
return 0;
} 
