不明白为什么大佬们一眼就看出这是最小割……
所以总而言之这就是一个最小割我也不知道为什么
然后边数太多直接跑会炸，所以要把平面图转对偶图，然后跑一个最短路即可
至于建图……请看代码我实在无能为力
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 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<class T>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 num 18 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)const 26 {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<node> 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 }