思路：
1.按照題意求最小割 轉換成最大流用Dinic解
2. 轉換成對偶圖 求最短路
Dinic：
//By SiriusRen
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1100000
int n,m,first[N],next[N*6],v[N*6],w[N*6],tot,jy,ans,vis[N],S,T,xx,pos[N];
void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}
void add(int x,int y,int z){Add(x,y,z),Add(y,x,z);}
bool tell(){
memset(vis,-1,sizeof(vis)),vis[S]=0;
queue<int>q;q.push(S);
while(!q.empty()){
int t=q.front();q.pop();
for(int i=first[t];~i;i=next[i])
if(w[i]&&vis[v[i]]==-1)
vis[v[i]]=vis[t]+1,q.push(v[i]);
}return vis[T]!=-1;
}
int zeng(int x,int y){
if(x==T)return y;
int r=0;
for(int i=first[x];~i&&y>r;i=next[i])
if(w[i]&&vis[v[i]]==vis[x]+1){
int t=zeng(v[i],min(y-r,w[i]));
w[i]-=t,w[i^1]+=t,r+=t;
}
if(!r)vis[x]=-1;
return r;
}
int main(){
memset(first,-1,sizeof(first));
scanf("%d%d",&n,&m);
S=m+1,T=n*m+m;
for(int i=1;i<=n;i++)for(int j=1;j<m;j++)
scanf("%d",&xx),add(i*m+j,i*m+j+1,xx);
for(int i=1;i<n;i++)for(int j=1;j<=m;j++)
scanf("%d",&xx),add(i*m+j,(i+1)*m+j,xx);
for(int i=1;i<n;i++)for(int j=1;j<m;j++)
scanf("%d",&xx),add(i*m+j,(i+1)*m+j+1,xx);
while(tell())while(jy=zeng(S,0x3fffffff))ans+=jy;
printf("%d\n",ans);
} //By SiriusRen
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
#define M 1111*1111*6
int n,m,a[1005][1005],b[1005][1005],c[1005][1005],T=2000*1005;
int first[M/3],next[M],v[M],w[M],tot,vis[M/3],d[M/3];
void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}
struct Node{int now,weight;}jy;
bool operator < (Node a,Node b){return a.weight>b.weight;}
void Dijkstra(){
priority_queue<Node>pq;pq.push(jy);
while(!pq.empty()){
Node t=pq.top();pq.pop();
if(vis[t.now])continue;
for(int i=first[t.now];~i;i=next[i])if(d[v[i]]>d[t.now]+w[i])
d[v[i]]=d[t.now]+w[i],jy.now=v[i],jy.weight=d[v[i]],pq.push(jy);
}printf("%d\n",d[T]=0x3f3f3f3f?d[T]:0);
}
void add(int x,int y,int z){Add(x,y,z),Add(y,x,z);}
int main(){
memset(first,-1,sizeof(first)),memset(d,0x3f,sizeof(d)),d[0]=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)for(int j=1;j<m;j++)scanf("%d",&a[i][j]);
for(int i=1;i<n;i++)for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
for(int i=1;i<n;i++)for(int j=1;j<m;j++)scanf("%d",&c[i][j]);
if(n==1||m==1){
if(m==1)for(int i=1;i<n;i++)d[T]=min(d[T],b[i][1]);
if(n==1)for(int i=1;i<m;i++)d[T]=min(d[T],a[1][i]);
}
for(int i=1;i<n;i++)for(int j=1;j<m;j++){
int cnt=((i-1)*(m-1)+j)*2;
add(cnt-1,cnt,c[i][j]);
if(j!=m-1)add(cnt-1,cnt+2,b[i][j+1]);
if(i!=n-1)add(cnt,cnt+(m-1)*2-1,a[i+1][j]);
}
for(int i=1;i<n;i++)add(((i-1)*(m-1)+1)*2,T,b[i][1]),add(0,2*i*(m-1)-1,b[i][m]);
for(int i=1;i<m;i++)add(0,2*i-1,a[1][i]),add(2*((n-2)*(m-1)+i),T,a[n][i]);
Dijkstra();
}