本题让我们求这张图的最小割，最小割等于最大流
下副代码
#include<bits/stdc++.h> #define eho(x) for(int& i=hed[x];~i;i=net[i]) #define Eho(x) for(int i=head[x];~i;i=net[i]) #define N 1000007 #define M 6000007 #define dre(x,y) (((x)-1)*(m)+(y)) #define sight(c) (c<='9'&&c>='0') #define INF (1<<20) using namespace std; int n,m,C; char c; void read(int &x){ c=getchar(); for(;!sight(c);c=getchar()); for(x=0;sight(c);c=getchar()) x=(x<<3)+(x<<1)+c-48; } struct G{ int head[N],net[M],fall[M],cost[M],s,t,tot,d[N],hed[N]; bool in[N]; queue<int> Q; G() { memset(head,-1,sizeof head);tot=-1;} inline void add(int x,int y,int c){ fall[++tot]=y; net[tot]=head[x]; head[x]=tot; cost[tot]=c; } inline void adds(int x,int y,int c){ add(x,y,c); add(y,x,c);} inline bool spfa(){ memset(d,127,sizeof d); int x; d[s]=1; Q.push(s); in[s]=1; while (!Q.empty()) { x=Q.front(); Q.pop(); Eho(x) if (cost[i]&&d[fall[i]]>d[x]+1) { d[fall[i]]=d[x]+1; if (!in[fall[i]]) {in[fall[i]]=1,Q.push(fall[i]);} } in[x]=0; } return d[t]<INF; } inline int dfs(int x,int F){ if (x==t|| !F) return F; int flow=0,r; eho(x) if (d[x]+1==d[fall[i]]&&((r=dfs(fall[i],min(F,cost[i])))>0)) { cost[i]-=r; cost[i^1]+=r; F-=r; flow+=r; if (!F) break;} return flow; } int dinic(int A,int B){ s=A; t=B; int flow=0; while (spfa()) { memcpy(hed,head,sizeof head); flow+=dfs(s,INF); } return flow; } }G; int main () { read(n); read(m); for (int i=1;i<=n;i++) for (int j=1;j<m;j++) read(C),G.adds(dre(i,j),dre(i,j+1),C); for (int i=1;i<n;i++) for (int j=1;j<=m;j++) read(C),G.adds(dre(i,j),dre(i+1,j),C); for (int i=1;i<n;i++) for (int j=1;j<m;j++) read(C),G.adds(dre(i,j),dre(i+1,j+1),C); printf("%d ",G.dinic(1,dre(n,m))); return 0; }