分析
我们不难想到所有点的海拔要么是0要么是1
所以跑最小割即可
但是时间复杂度不行
于是转化为对偶图的最短路
代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<queue> #include<ctime> #include<vector> #include<set> #include<map> #include<stack> using namespace std; #define int long long int n,m,d[300100],vis[300100],s,t; int head[2000100],to[2000100],nxt[2000100],w[2000100],cnt; priority_queue<pair<int,int> >q; inline void add(int x,int y,int z){ nxt[++cnt]=head[x]; head[x]=cnt; to[cnt]=y; w[cnt]=z; } inline int getwh(int x,int y){ if(x==n||y==0)return s; if(x==0||y==n)return t; return (x-1)*(n-1)+y; } inline void dij(){ memset(d,0x3f,sizeof(d)); q.push(make_pair(0,s));d[s]=0; while(!q.empty()){ int x=q.top().second;q.pop(); if(vis[x])continue;vis[x]=1; for(int i=head[x];i;i=nxt[i]){ int y=to[i]; if(d[y]>d[x]+w[i]){ d[y]=d[x]+w[i]; q.push(make_pair(-d[y],y)); } } } } signed main(){ int i,j,k; scanf("%lld",&n); n++; s=n*n+20,t=n*n+21; for(i=1;i<=n;i++) for(j=1;j<n;j++){ int x; scanf("%lld",&x); add(getwh(i,j),getwh(i-1,j),x); } for(i=1;i<n;i++) for(j=1;j<=n;j++){ int x; scanf("%lld",&x); add(getwh(i,j-1),getwh(i,j),x); } for(i=1;i<=n;i++) for(j=1;j<n;j++){ int x; scanf("%lld",&x); add(getwh(i-1,j),getwh(i,j),x); } for(i=1;i<n;i++) for(j=1;j<=n;j++){ int x; scanf("%lld",&x); add(getwh(i,j),getwh(i,j-1),x); } dij(); printf("%lld\n",d[t]); return 0; }