题目链接：戳我
看到输出格式。。。。如果有小数的话为什么需要保留到整数呢。。。所以——
并没有小数！我们可以认为每个点的海拔要么是1要么是0.然后求最小割就可以了！
至于为什么要么是1要么是0？蒟蒻yy的证明：既然是求出来最小割，如果差是1的话就可以割掉这条边了，这样对最小值（比如说x）加权为1。如果不是差1，那么显然对于这个点，我们就不能割一条边了事了，至少需要割掉两条边（比如说x,x'，其中x'>x），这样虽然每个边的值加权是个小于一的小数，但是总和加起来还是没有前面的小。
既然是最小割，我们直接求不就好了！
数据范围有点大，显然裸的最小割跑不过去。这时候我们就要优化了！启用平面图转对偶图，用dijkstra+priority_queue优化求最短路。
最后注意建图方式，源点在左下角，汇点在右上角，这样才能用最短路求出来最小割。（别像我智障地一开始把源点建到了左上，汇点右下，还以为自己什么都没写错qwqwq）
连边的话，显然是原图向右的连成向下的，向下的连成向右的，向左的连成向上的，向上的连成向左的，这样才能求出来最小割。（原图向左向上的边别不连！因为有可能最小割比较曲折。。。。。）
此外还有一个建图小技巧吧。。从yyb dalao那里学的，直接用数组存序号就行了。。。这样就不用每次都写诸如(i-1)*m+j的东西了。。。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define S 0
#define T cnt+1
#define MAXN 4000010
using namespace std;
int n,m,t,cur,cnt;
int dis[MAXN],done[MAXN],head[MAXN],id[510][510];
struct Node
{
int u,d;
friend bool operator <(struct Node x,struct Node y)
{return x.d>y.d;}
};
struct Edge{int nxt,to,dis;}edge[MAXN<<1];
inline void add(int from,int to,int dis)
{edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,head[from]=t;}
inline void dij(int s,int t)
{
priority_queue<Node>q;
memset(dis,0x3f,sizeof(dis));
memset(done,0,sizeof(done));
q.push((Node){s,0});dis[s]=0;
while(!q.empty())
{
int u=q.top().u; q.pop();
if(done[u]) continue;
done[u]=1;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(dis[u]+edge[i].dis<dis[v])
dis[v]=dis[u]+edge[i].dis,q.push((Node){v,dis[v]});
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
id[i][j]=++cnt;
for(int i=1;i<=n;i++) id[0][i]=id[i][0]=S,id[i][n+1]=id[n+1][i]=T;
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&cur);
add(id[i-1][j],id[i][j],cur);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)
{
scanf("%d",&cur);
add(id[i][j-1],id[i][j],cur);
}
for(int i=0;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&cur);
add(id[i+1][j],id[i][j],cur);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)
{
scanf("%d",&cur);
add(id[i][j],id[i][j-1],cur);
}
dij(S,T);
printf("%d
",dis[T]);
return 0;
}