题面
https://www.luogu.org/problem/P2046
题解
首先，显然，一个地方的高度不是$0$，就是$1$。
我们设计一个网络流模型，保留原图中的边，以$(1,1)$为源，$(n,n)$为汇，求最小割（纯口胡，正确性不敢保证）
接着因为数据太大，平面图转对偶图。
平面图最小割即对偶图最短路，
我们把左、上边沿外点记为$S$，下、右边沿外的点记为$T$，
原来的向下的人流变成向右的路径（为什么？因为向下的人流代表了上面是$0$，而下面是$1$，$S$在左而$T$在右，所以从左到右）
向上的人流变成向左的路径（下$0$上$1$，只有路径向左走时才会出现这样的情况）
左右方向的人流同理。
虽然这样正边和反边的权值不一样，有点难理解，但只要按照那套理论和画的图像一步步推就可以了。
刚开始拿到这道题的时候，想到这个细节，觉得不可做，但是再仔细想想就会做了。要是在考试的时候这样可不行啊。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> #define ri register int #define LL long long #define N 300050 #define S 0 #define T (n*n+1) using namespace std; inline int read() { int ret=0,f=0; char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0' && ch<='9') ret*=10,ret+=(ch-'0'),ch=getchar(); return f?-ret:ret; } int n,id[550][550]; LL dis[N]; bool vis[N]; vector<int> to[N],len[N]; struct HeapNode { int u; LL d; bool operator < (const HeapNode &rhs) const { return d>rhs.d; } }; void add_edge(int u,int v,int w) { to[u].push_back(v); len[u].push_back(w); } LL dijkstra() { priority_queue<HeapNode> pq; memset(dis,0x3f,sizeof(dis)); dis[S]=0; pq.push((HeapNode){S,dis[S]}); while (!pq.empty()) { int x=pq.top().u; pq.pop(); if (vis[x]) continue; vis[x]=1; for (ri i=0;i<to[x].size();++i) { int y=to[x][i]; if (dis[x]+len[x][i]<dis[y]) { dis[y]=dis[x]+len[x][i]; pq.push((HeapNode){y,dis[y]}); } } } return dis[T]; } int main() { n=read(); int cc=0; for (ri i=1;i<=n;++i) for (ri j=1;j<=n;++j) id[i][j]=++cc; for (ri i=1;i<=n;++i) id[n+1][i]=id[i][0]=S,id[i][n+1]=id[0][i]=T; for (ri i=1;i<=n+1;++i) for (ri j=1;j<=n;++j) add_edge(id[i][j],id[i-1][j],read()); for (ri i=1;i<=n;++i) for (ri j=1;j<=n+1;++j) add_edge(id[i][j-1],id[i][j],read()); for (ri i=1;i<=n+1;++i) for (ri j=1;j<=n;++j) add_edge(id[i-1][j],id[i][j],read()); for (ri i=1;i<=n;++i) for (ri j=1;j<=n+1;++j) add_edge(id[i][j],id[i][j-1],read()); printf("%lld ",dijkstra()); return 0; }