最短路+对偶图
看这题最容易想到的就是网络流。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=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),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[1996005],cnt,hd[1996005],nxt[6000000],ed[1996005],poi[6000000],dis[6000000]; 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-1)*(m-1)*2+1; t=s+1; //左上/右下为虚拟起点/终点 for(int i=1;i<=n;++i) for(int j=1;j<m;++j){ q1= i<n ? (i-1)*(m-1)*2+j:s,q2= i>1 ? (i-2)*(m-1)*2+m-1+j:t,read(q3); //给每个块编号 add(q1,q2,q3); add(q2,q1,q3); } for(int i=1;i<n;++i) for(int j=1;j<=m;++j){ q1= j<m ? (i-1)*(m-1)*2+m-1+j:t,q2= j>1 ? (i-1)*(m-1)*2+j-1:s,read(q3); add(q1,q2,q3); add(q2,q1,q3); } for(int i=1;i<n;++i) for(int j=1;j<m;++j){ q1=(i-1)*(m-1)*2+j,q2=q1+m-1,read(q3); add(q1,q2,q3); add(q2,q1,q3); } memset(d,127,sizeof(d)); h.push((data){d[s]=0,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 0; }