最短路+对偶图
看这题最容易想到的就是网络流。Dinic可以过，据说还跑得比正解快。
如果不写网络流，那么需要知道2个前置知识：平面图和对偶图（右转baidu）
我们把图转成对偶图。特别的，图外面的空间沿左上-右下（起点-终点）切开，作为虚拟起点/终点。
然后我们就可以愉快地跑一遍最短路了。因为对偶图中的最短路就等于平面图中的最小割。
我们可以把问题看成：左上和右下各有一个电源，现在它们短路。给出电线的价值，求如何用最小的代价剪断若干条电线（不能拆吗），让这两个电源之间没有电线直接连接。
构图？瞎搞。但是vector会MLE一个点（姿势不行TAT），所以用邻接表存边，套一个堆优化dijkstra就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cctype>
using namespace std;
template <typename T> inline void read(T &x){
char c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
}
struct data{
int d,u;
bool operator < (const data &tmp) const {return d>tmp.d;}
}; priority_queue <data> h;
int n,m,s,t,d[],cnt,hd[],nxt[],ed[],poi[],dis[];
inline void add(int x,int y,int v){
nxt[ed[x]]=++cnt; hd[x]=hd[x] ? hd[x]:cnt;
ed[x]=cnt; poi[cnt]=y; dis[cnt]=v;
}
int main(){
read(n); read(m); int q1,q2,q3;
s=(n-)*(m-)*+; t=s+; //左上/右下为虚拟起点/终点
for(int i=;i<=n;++i)
for(int j=;j<m;++j){
q1= i<n ? (i-)*(m-)*+j:s,q2= i> ? (i-)*(m-)*+m-+j:t,read(q3); //给每个块编号
add(q1,q2,q3); add(q2,q1,q3);
}
for(int i=;i<n;++i)
for(int j=;j<=m;++j){
q1= j<m ? (i-)*(m-)*+m-+j:t,q2= j> ? (i-)*(m-)*+j-:s,read(q3);
add(q1,q2,q3); add(q2,q1,q3);
}
for(int i=;i<n;++i)
for(int j=;j<m;++j){
q1=(i-)*(m-)*+j,q2=q1+m-,read(q3);
add(q1,q2,q3); add(q2,q1,q3);
}
memset(d,,sizeof(d));
h.push((data){d[s]=,s});
while(!h.empty()){ //裸的堆优化dj
data x=h.top(); h.pop();
if(x.d!=d[x.u]) continue;
for(int i=hd[x.u];i;i=nxt[i]){
if(x.d+dis[i]<d[poi[i]]){
d[poi[i]]=x.d+dis[i];
if(poi[i]!=t) h.push((data){d[poi[i]],poi[i]});
}
}
}printf("%d",d[t]);
return ;
}