题链：

题解：

网络流、最小割、对偶图

奇妙的题 ~

种种原因导致了高度要么为 0，要么为 1 (1),然后 0,1区域是分离的 (2)。

对于 (2) 是显然的，因为如果在一片 1的区域中出现了一个 0，那么把 0改为 1一定会更优。

而对于 (1) ，就只有感性一点理解了（没看到一个比较理性的讲解）。

    由于左上角为 0，右下角为 1，所以总会存在有上坡路。

    那么为了使上坡导致的体力消耗最少，我们会去选择一条流量小(流量设为w)的路从 0直接爬向 1，

    这样才是最优的。

    如果此时不一次性爬上去，而是爬部分高度 h (0<h<1) 那么以后也必然会爬到 1，

    但那时流量的大小就不如之前的 w小了，所以总的消耗是大于在流量小的边一次性爬上 1的。

所以至此，求出左上角 S ->右下角 T 的最小割便是答案了。

（这条割把图分为了 0部 和 1部）

但是跑网络流会超时。

由于图的特殊性——非常规则，

所以就把中间的各个区域抽象成一个个的点，

图的左下的空白区域看成是 S点，

图的右上的空白区域看成是 T点，

然后按照（"左手定则"，诶呀，管的怎么建的，符合题意就可以了）一定的方向把原图的边变为与它垂直的边（边权不变），连接新的那些点，

最后跑一个更加高效的最短路算法，求出S->T的最短路就是答案了。

（可以感性理解为是在模拟去割那张图）。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #define MAXN 300000#define MAXM 3000000#define ll long longusing namespace std;struct Edge{	ll to[MAXM],val[MAXM],nxt[MAXM],head[MAXN],ent;	void Init(){ent=2;}//记得初始化 	void Adde(ll u,ll v,ll w){		to[ent]=v; val[ent]=w; nxt[ent]=head[u]; head[u]=ent++;	}	ll Next(ll i,bool type){		return type?head[i]:nxt[i];	}}E;ll dis[MAXN];ll N;ll idx(ll i,ll j){	return (i-1)*N+j;}ll Dijkstra(ll S,ll T){	typedef pair
        
         pii;	static bool vis[MAXN];	memset(vis,0,sizeof(vis));	memset(dis,0x3f,sizeof(dis)); ll u,v;	priority_queue
         
          
           ,greater
           
             >q; q.push(make_pair(0,S)); dis[S]=0; while(!q.empty()){ u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(ll i=E.Next(u,1);i;i=E.Next(i,0)){ v=E.to[i]; if(vis[v])continue; if(dis[v]<=dis[u]+E.val[i]) continue; dis[v]=dis[u]+E.val[i]; q.push(make_pair(dis[v],v)); } } return dis[T];}int main(){ freopen("altitude.in","r",stdin);freopen("altitude.out","w",stdout); E.Init(); ll S,T; scanf("%lld",&N); S=N*N+1; T=S+1; for(ll i=1,x,from,to;i<=N+1;i++) for(ll j=1;j<=N;j++){ scanf("%lld",&x); from=i==N+1?S:idx(i,j); to=i==1?T:idx(i-1,j); E.Adde(from,to,x); } for(ll i=1,x,from,to;i<=N;i++) for(ll j=1;j<=N+1;j++){ scanf("%lld",&x); from=j==1?S:idx(i,j-1); to=j==N+1?T:idx(i,j); E.Adde(from,to,x); } for(ll i=1,x,from,to;i<=N+1;i++) for(ll j=1;j<=N;j++){ scanf("%lld",&x); from=i==1?T:idx(i-1,j); to=i==N+1?S:idx(i,j); E.Adde(from,to,x); } for(ll i=1,x,from,to;i<=N;i++) for(ll j=1;j<=N+1;j++){ scanf("%lld",&x); from=j==N+1?T:idx(i,j); to=j==1?S:idx(i,j-1); E.Adde(from,to,x); } ll ans=Dijkstra(S,T); printf("%lld",ans); return 0;}