不明白为什么大佬们一眼就看出这是最小割……
所以总而言之这就是一个最小割我也不知道为什么
然后边数太多直接跑会炸，所以要把平面图转对偶图，然后跑一个最短路即可
至于建图……请看代码我实在无能为力
1 //minamoto 2 #include3 #include 4 #include 5 #include 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 template inline bool cmin(T&a,const T&b){ return a>b?a=b,1:0;}10 inline int read(){11 #define num ch-'0'12 char ch;bool flag=0;int res;13 while(!isdigit(ch=getc()))14 (ch=='-')&&(flag=true);15 for(res=num;isdigit(ch=getc());res=res*10+num);16 (flag)&&(res=-res);17 #undef num18 return res;19 }20 const int N=1e6+5,M=2e6+5;21 struct node{22 int u,dis;23 node(){}24 node(int u,int dis):u(u),dis(dis){}25 inline bool operator <(const node &b)const26 { return dis>b.dis;}27 };28 int head[N],ver[M],edge[M],Next[M],tot;29 int dis[N],vis[N];30 int n,S,T,x;31 priority_queue q;32 inline void add(int u,int v,int e){33 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;34 }35 int spfa(){36 memset(dis,0x3f,sizeof(dis));37 memset(vis,0,sizeof(vis));38 q.push(node(S,0)),dis[S]=0;39 while(!q.empty()){40 int u=q.top().u;q.pop();41 if(vis[u]) continue;42 vis[u]=1;43 for(int i=head[u];i;i=Next[i]){44 int v=ver[i];45 if(cmin(dis[v],dis[u]+edge[i]))46 q.push(node(v,dis[v]));47 }48 }49 return dis[T];50 }51 int main(){52 // freopen("testdata.in","r",stdin);53 n=read();S=n*n+1,T=S+1;54 for(int i=0;i<=n;++i)55 for(int j=1;j<=n;++j){56 x=read();57 i==0?add(j,T,x):i==n?add(S,(i-1)*n+j,x):add(i*n+j,(i-1)*n+j,x);58 }59 for(int i=1;i<=n;++i)60 for(int j=0;j<=n;++j){61 x=read();62 j==0?add(S,(i-1)*n+j+1,x):j==n?add(i*n,T,x):add((i-1)*n+j,(i-1)*n+j+1,x);63 }64 for(int i=0;i<=n;++i)65 for(int j=1;j<=n;++j){66 x=read();67 i==0?add(T,j,x):i==n?add((i-1)*n+j,S,x):add((i-1)*n+j,i*n+j,x);68 }69 for(int i=1;i<=n;++i)70 for(int j=0;j<=n;++j){71 x=read();72 j==0?add((i-1)*n+j+1,S,x):j==n?add(T,i*n,x):add((i-1)*n+j+1,(i-1)*n+j,x);73 }74 printf("%d\n",spfa());75 return 0;76 }