首先注意到，把一个点的海拔定为>1的数是毫无意义的。实际上，可以转化为把这些点的海拔要么定为0，要么定为1.
其次，如果一个点周围的点的海拔没有和它相同的，那么这个点的海拔也是可以优化的，即把这个点变为周围海拔一样的显然能使结果变优。
于是问题就变成了，这个图的海拔为0的联通块和起点连在一起，海拔为1的联通块和终点连在一起。
此即为经典的最小割。
由于此图为平面图，我们可以使用平面图最小割转对偶图最短路优化算法。
因为这是有向图，因此构建对偶图的时候注意边的方向即可。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-7 # define MOD 1024523 # define INF 1e16 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { 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*10+ch-'0';ch=getchar();} return x*f; } void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0'); } const int N=250005; //Code begin... struct Edge{int p, next; LL w;}edge[N*40]; struct qnode{ int v; LL c; qnode(int _v=0, LL _c=0):v(_v),c(_c){} bool operator<(const qnode&r)const{return c>r.c;} }; bool vis[N]; int head[N], cnt=1; LL G1[505][505], G2[505][505], G3[505][505], G4[505][505], dist[N]; priority_queue<qnode>que; void add_edge(int u, int v, LL w){edge[cnt].p=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;} void Dijkstra(int n, int start){ mem(vis,false); FOR(i,0,n) dist[i]=INF; dist[start]=0; que.push(qnode(start,0)); qnode tmp; while (!que.empty()) { tmp=que.top(); que.pop(); int u=tmp.v; if (vis[u]) continue; vis[u]=true; for (int i=head[u]; i; i=edge[i].next) { int v=edge[i].p; LL cost=edge[i].w; if (!vis[v]&&dist[v]>dist[u]+cost) dist[v]=dist[u]+cost, que.push(qnode(v,dist[v])); } } } int main () { int n, s, t, x; scanf("%d",&n); s=0; t=n*n+1; FOR(i,0,n) FOR(j,1,n) scanf("%lld",&G1[i][j]); FOR(i,1,n) FOR(j,0,n) scanf("%lld",&G2[i][j]); FOR(i,0,n) FOR(j,1,n) scanf("%lld",&G3[i][j]); FOR(i,1,n) FOR(j,0,n) scanf("%lld",&G4[i][j]); FOR(i,0,n) FOR(j,1,n) { if (i==0) add_edge(s,i*n+j,G1[i][j]), add_edge(i*n+j,s,G3[i][j]); else if (i==n) add_edge((i-1)*n+j,t,G1[i][j]), add_edge(t,(i-1)*n+j,G3[i][j]); else add_edge((i-1)*n+j,i*n+j,G1[i][j]), add_edge(i*n+j,(i-1)*n+j,G3[i][j]); } FOR(i,1,n) FOR(j,0,n) { if (j==0) add_edge((i-1)*n+j+1,t,G2[i][j]), add_edge(t,(i-1)*n+j+1,G4[i][j]); else if (j==n) add_edge(s,(i-1)*n+j,G2[i][j]), add_edge((i-1)*n+j,s,G4[i][j]); else add_edge((i-1)*n+j+1,(i-1)*n+j,G2[i][j]), add_edge((i-1)*n+j,(i-1)*n+j+1,G4[i][j]); } Dijkstra(t,s); printf("%lld ",dist[t]); return 0; }