容易想到原图由海拔高度划分成两大连通块。
于是就可以套上最小割了。
由于点数过多，可以将网络流最小割转换为其对偶图最短路。
#include<bits/stdc++.h> using namespace std; int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48); ch=getchar();} return x*f; } int n,cnt=2; int col[505][505],tot,dis[1000050]; int head[1000050],nex[2000050],ver[2000050],edg[2000050]; priority_queue<pair<int ,int > >q; bool vis[1000050]; void add(int x,int y,int z) { ++tot;nex[tot]=head[x];head[x]=tot;ver[tot]=y;edg[tot]=z; } void spfa() { memset(dis,127/2,sizeof(dis)); dis[1]=0; q.push(make_pair(0,1)); while(!q.empty()) { int u=q.top().second; q.pop(); vis[u]=false; for(int i=head[u];i;i=nex[i]) { int v=ver[i]; if(dis[v]>dis[u]+edg[i]) { dis[v]=dis[u]+edg[i]; if(!vis[v]) { vis[v]=true; q.push(make_pair(-dis[v],v)); } } } } } int main() { n=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) col[i][j]=++cnt; for(int i=1;i<=n;++i) col[i][0]=col[n+1][i]=1; for(int i=1;i<=n;++i) col[0][i]=col[i][n+1]=2; for(int i=1;i<=n+1;++i) for(int j=1;j<=n;++j) add(col[i][j],col[i-1][j],read()); for(int i=1;i<=n;++i) for(int j=0;j<=n;++j) add(col[i][j],col[i][j+1],read()); for(int i=0;i<=n;++i) for(int j=1;j<=n;++j) add(col[i][j],col[i+1][j],read()); for(int i=1;i<=n;++i) for(int j=1;j<=n+1;++j) add(col[i][j],col[i][j-1],read()); spfa(); printf("%d",dis[2]); return 0; }