虽然最小割能过，但好像并不是官方解法
此题正解应是平面图转对偶图
所谓“对偶图”，其实就是将给定图的每块区域看成点，如果有一条边分隔开了两块区域，那么就在这两块区域之间连边。
对于这道题，我们连完边之后再跑一遍最短路就好了
另外要注意的是特判(n=1)或(m=1)的情况
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct zzz{
int t,len,nex;
}e[3000010<<1]; int head[3000010],tot;
void add(int x,int y,int z){
e[++tot].len=z;
e[tot].t=y;
e[tot].nex=head[x];
head[x]=tot;
}
int read(){
int k=0; char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
k=k*10+c-48,c=getchar();
return k;
}
struct hhh{
int l,k;
bool operator < (const hhh &y) const { return l > y.l; };
};
priority_queue <hhh> q; int dis[3000010];
int dijstra(int s,int t){
memset(dis,127,sizeof(dis));
q.push((hhh){0,s}); dis[s]=0;
while(!q.empty()){
int k=q.top().k;
if(q.top().l!=dis[k]){
q.pop(); continue;
} q.pop();
for(int i=head[k];i;i=e[i].nex){
if(dis[k]+e[i].len < dis[e[i].t]){
dis[e[i].t]=dis[k]+e[i].len;
q.push((hhh){dis[e[i].t],e[i].t});
}
}
}
return dis[t];
}
int main(){
int n=read(),m=read();
if(n==1){
int ans=2147483647;
for(int i=1;i<=m-1;i++)
ans=min(ans,read());
cout<<ans; return 0;
}
if(m==1){
int ans=2147483647;
for(int i=1;i<=n-1;i++)
ans=min(ans,read());
cout<<ans; return 0;
}
int s=3000000,t=3000001;
for(int i=1,cnt=0;i<=n;++i,cnt+=m-1)
for(int j=1;j<=m-1;++j){
int x=read(); ++cnt;
if(i==1)
add(cnt,t,x), add(t,cnt,x);
else if(i==n)
add(s,cnt-m+1,x), add(cnt-m+1,s,x);
else
add(cnt,cnt-m+1,x), add(cnt-m+1,cnt,x);
}
for(int i=1,cnt=m-1;i<=n-1;++i,cnt+=m-2)
for(int j=1;j<=m;++j){
int x=read(); ++cnt;
if(j==1)
add(s,cnt,x), add(cnt,s,x);
else if(j==m)
add(cnt-m,t,x), add(t,cnt-m,x);
else
add(cnt-m,cnt,x), add(cnt,cnt-m,x);
}
for(int i=1,cnt=0;i<=n-1;++i,cnt+=m-1)
for(int j=1;j<=m-1;j++){
int x=read(); ++cnt;
add(cnt+m-1,cnt,x), add(cnt,cnt+m-1,x);
}
printf("%d",dijstra(s,t));
return 0;
}